从右往左扫描线，用线段树维护扫描线上每一个点能达到的花的数量，并支持最近篱笆的查询。

对于一朵花，找到它上方最近的篱笆，那么它对这中间的每头牛的贡献都是$1$。

当扫到一个篱笆的右边界时，这中间的答案都要清零。

当扫到一个篱笆的左边界时，这中间的答案同理都要清零，但是要向上直到最近的篱笆为止都加上下面的答案。

这中间对这个篱笆右下角的贡献会重复计数，因此需要减掉。

时间复杂度$O(n\log n)$。

 

#include
     
      #include
      
       const int N=1000005,M=2100000,U=200010;int n,m,cnt,i,v[M],ta[M],tc[M],f[U],ans[U];struct E{  int x,l,r,t,i;  E(){}  E(int _x,int _l,int _r,int _t,int _i){x=_x,l=_l,r=_r,t=_t,i=_i;}}e[U*5];inline bool cmp(const E&a,const E&b){  if(a.x!=b.x)return a.x>b.x;  if(a.t!=b.t)return a.t
       
        ='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void taga1(int x,int p){if(~tc[x])tc[x]+=p;else ta[x]+=p;}inline void tagc1(int x,int p){ta[x]=0;tc[x]=p;}inline void pb(int x){  if(ta[x])taga1(x<<1,ta[x]),taga1(x<<1|1,ta[x]),ta[x]=0;  if(~tc[x])tagc1(x<<1,tc[x]),tagc1(x<<1|1,tc[x]),tc[x]=-1;}void change(int x,int a,int b,int c,int p){  if(a==b){v[x]=p?a:0;return;}  int mid=(a+b)>>1;  c<=mid?change(x<<1,a,mid,c,p):change(x<<1|1,mid+1,b,c,p);  v[x]=v[x<<1|1]?v[x<<1|1]:v[x<<1];}int get(int x,int a,int b,int d){  if(b<=d)return v[x];  int mid=(a+b)>>1,t=0;  if(d>mid)t=get(x<<1|1,mid+1,b,d);  if(t)return t;  return get(x<<1,a,mid,d);}void add(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){taga1(x,p);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)add(x<<1,a,mid,c,d,p);  if(d>mid)add(x<<1|1,mid+1,b,c,d,p);}void clear(int x,int a,int b,int c,int d){  if(c<=a&&b<=d){tagc1(x,0);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)clear(x<<1,a,mid,c,d);  if(d>mid)clear(x<<1|1,mid+1,b,c,d);}int ask(int x,int a,int b,int c){  if(a==b)return ta[x]+tc[x];  pb(x);  int mid=(a+b)>>1;  return c<=mid?ask(x<<1,a,mid,c):ask(x<<1|1,mid+1,b,c);}int main(){  read(m);  for(i=1;i<=m;i++){    int xl,xr,yl,yr;    read(xl),read(yl),read(xr),read(yr);    e[++cnt]=E(yr,xl,xr,-2,0);    e[++cnt]=E(yl-1,xl,xr,-1,i);    e[++cnt]=E(yr+1,xr+1,0,1,-i);  }  read(m);  while(m--){    int x,y;    read(x),read(y);    e[++cnt]=E(y,x,0,0,0);  }  read(n);  for(i=1;i<=n;i++){    int x,y;    read(x),read(y);    e[++cnt]=E(y,x,0,1,i);  }  std::sort(e+1,e+cnt+1,cmp);  for(i=1;i<=cnt;i++){    int l=e[i].l,r=e[i].r;    if(e[i].t==-1){      change(1,0,N,l-1,0);      change(1,0,N,r,0);      int o=get(1,0,N,l-1);      clear(1,0,N,l,r);      add(1,0,N,o+1,r,ask(1,0,N,r+1));      if(o+1<=l-1&&f[e[i].i])add(1,0,N,o+1,l-1,-f[e[i].i]);    }else if(e[i].t==-2){      change(1,0,N,l-1,1);      change(1,0,N,r,1);      clear(1,0,N,l,r);    }else if(!e[i].t)add(1,0,N,get(1,0,N,l-1)+1,l,1);    else{      if(e[i].i>0)ans[e[i].i]=ask(1,0,N,l);      else f[-e[i].i]=ask(1,0,N,l);    }  }  for(i=1;i<=n;i++)printf("%d\n",ans[i]);  return 0;}