从右往左扫描线,用线段树维护扫描线上每一个点能达到的花的数量,并支持最近篱笆的查询。
对于一朵花,找到它上方最近的篱笆,那么它对这中间的每头牛的贡献都是$1$。
当扫到一个篱笆的右边界时,这中间的答案都要清零。
当扫到一个篱笆的左边界时,这中间的答案同理都要清零,但是要向上直到最近的篱笆为止都加上下面的答案。
这中间对这个篱笆右下角的贡献会重复计数,因此需要减掉。
时间复杂度$O(n\log n)$。
#include<cstdio>
#include<algorithm>
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<b.t;
return a.l<b.l;
}
inline void read(int&a){char c;while(!(((c=getchar())>='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;
}