数点问题

发表于 更新于 分类于 阅读次数： Changyan：

数点问题

二维数点

平面有n个点，回答q个询问，每个询问给定$[x_1,y_1]\cdot[x_2,y_2]$,求在这个范围内的点数

做法1：CDQ分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#define N 1000010
struct Pos{
	int x,y,z,p,id,sum;
	bool operator<(const Pos&W)const{
		if(x!=W.x) return x<W.x;
		if(y!=W.y) return y<W.y;
		return z < W.z;
	}
}p[N],tmp[N];
int n,m,idx,ans[N];

void merge(int l,int r){
	if(l>=r) return ;
	int mid=l+r>>1;
	merge(l,mid); merge(mid+1,r);
	int i=l,j=mid+1,cnt=0;
	int sum=0;
	while(i<=mid&&j<=r){
		if(p[i].y<=p[j].y) sum += (!p[i].z), tmp[++cnt]=p[i++];
		else p[j].sum += sum, tmp[++cnt] = p[j++];
	}
	while(i<=mid) sum += (!p[i].z), tmp[++cnt]=p[i++];
	while(j<=r) p[j].sum += sum, tmp[++cnt] = p[j++];
	for(int i=l,j=1;i<=r;) p[i++]=tmp[j++];
}
//=================================
signed main(){
	n=read(),m=read();
	rep(i,1,n){
		int x=read(),y=read();
		p[++idx]={x,y,0,0,0,0};
	}
	for(int i=1;i<=m;++i){
		int x1=read(),x2=read(),y1=read(),y2=read();
		p[++idx]={x2,y2,1,1,i,0};
		p[++idx]={x1-1,y1-1,1,1,i,0};
		p[++idx]={x1-1,y2,1,-1,i,0};
		p[++idx]={x2,y1-1,1,-1,i,0};
	}
	sort(p+1, p+1+idx);
	merge(1,idx);
	for(int i=1;i<=idx;++i){
		if(p[i].z) 
			ans[p[i].id] += p[i].p*p[i].sum;
	}
	for(int i=1;i<=n;++i) print(ans[i]); 
	return 0;
}

CDQ分治是处理二维/三维数点问题非常高效的离线做法，能够做到时间复杂度O(nlogn)带非常小常数,空间复杂度O(n)

2.离线+树状数组

这种做法就是按照横坐标排序后对纵坐标离散化后用树状数组维护位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define N 1000010
struct BIT{
	int n,tr[N];
	#define lowbit(x) ((x)&(-x))
	void resize(int _n){n=_n;}
	void add(int x,int d){
		for(;x<=n;x+=lowbit(x)) tr[x]+=d;
	}
	LL ask(int x){
		LL ans=0;
		for(;x;x-=lowbit(x)) ans+=tr[x];
		return ans;
	}
}T;
int n,m,k,ans[N];
vector<int> alls;
int get(int x){
	return lower_bound(alls.begin(), alls.end(), x) - alls.begin()+1;
}
struct  Pos{
	int x,y,z,p;
	bool operator<(const Pos& W)const{
		if(x!=W.x) return x < W.x;
		return z<W.z;
	}
};
vector<Pos> q;
//=================================
signed main(){
	n=read(),m=read();
	rep(i,1,n){
		int x=read(),y=read();
		q.push_back({x,y,0,0});
		alls.push_back(y);
	}
	rep(i,1,m){
		int x1=read(),x2=read(),y1=read(),y2=read();
		q.push_back({x2,y2,i,1});
		q.push_back({x1-1,y1-1,i,1});
		q.push_back({x1-1,y2,i,-1});
		q.push_back({x2,y1-1,i,-1});
		alls.push_back(y1);
		alls.push_back(y2);
		alls.push_back(y1-1);
	}
	sort(alls.begin(), alls.end());
	alls.erase(unique(alls.begin(),alls.end()), alls.end());
	sort(q.begin(), q.end());
	T.resize(alls.size()+1);
	for(auto u:q){
		int x=u.x, y=u.y,z=u.z,p=u.p;
		y=get(y);
		if(z==0){
			T.add(y, 1);
		}
		else{
			int tmp=T.ask(y);
			ans[z]+=tmp*p;
		}
	}
	for(int i=1;i<=n;++i) print(ans[i]);
	return 0;
}