P2163 [SHOI2007]园丁的烦恼 题解

题目大意

给出一个二维平面内的 (n) 个点，每次询问一个矩形区间内点的个数

P2163 [SHOI2007]园丁的烦恼

solve

同样，这道题也有很多种解法，我们先转化一道

ans=S[c][d]-S[a-1][d]-S[b-1][c]+S[c-1][d-1]

题目也就变成了求前缀和

所以用二维偏序，在CDQ的时候查看有几个 (y) 在我前面的就好了，用不上树状数组，每次处理完保证 y 有序就可以了，有点类似于二路归并处理逆序对的想法，但由于CDQ分治的时候已经保证了 (L-mid) 的 (x) 小于 (mid-r) 的 (x) 所以处理 (y) 可以了

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+5;
struct qus{
	int x,y,opt,id;
	bool operator <(const qus &b)const {return x == b.x ? (y == b.y ? opt : y < b.y) : x < b.x;}
}q[maxn],tmp[maxn];
int tot,ans[maxn],N,M,ans_tot;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
void CDQ(int l,int r){
	if(l==r)return ;
	int mid=(r-l>>1)+l;
	CDQ(l,mid);CDQ(mid+1,r);
	int i=l,j=mid+1,pos=l,cnt=0;
	while(i<=mid&&j<=r){
		if(q[i].y<=q[j].y) cnt+=q[i].opt,tmp[pos++]=q[i++];
		else ans[q[j].id]+=cnt,tmp[pos++]=q[j++]; 
	}
	while(i<=mid)tmp[pos++]=q[i++];
	while(j<=r)ans[q[j].id]+=cnt,tmp[pos++]=q[j++];
	for(int i=l;i<=r;i++)q[i]=tmp[i];
}
int main(){
	freopen("P2163.in","r",stdin);
	freopen("P2163.out","w",stdout);
	N=read();M=read();
	for(int x,y,i=1;i<=N;i++) x=read(),y=read(),q[++tot]=(qus)qus{x,y,1,0};
	for(int a,b,c,d,i=1;i<=M;i++){
		a=read(),b=read(),c=read(),d=read();
		q[++tot]=(qus)qus{c,d,0,++ans_tot};
		q[++tot]=(qus)qus{c,b-1,0,++ans_tot};
		q[++tot]=(qus)qus{a-1,d,0,++ans_tot};
		q[++tot]=(qus)qus{a-1,b-1,0,++ans_tot};
	}
	sort(q+1,q+1+tot);
	CDQ(1,tot);
	for(int i=1;i+3<=ans_tot;i+=4){
		printf("%d
",ans[i]-ans[i+1]-ans[i+2]+ans[i+3]);
	}
	return 0;
}