【cdq分治】三维偏序

分治

传送台:LOJ112

吐槽一下cdq分治模板题好难找啊！！！

思路：题意相当于求三维坐标系中一个点的左下角有几个点（这难道不是数点？）

如果考虑二维坐标系中，那么只需对一维排序，另一维求最长不下降子序列。

然而三维中一维排完序还有两维（真悲伤）。

考虑分治，首先如果点A对点B的答案产生贡献，那$必定有x_A\leqslant x_B,y_A\leqslant y_B,z_A\leqslant z_B$；

那如果所有点按x为第一关键字，y为第二关键字，z位第三关键字排序，排名靠右的点一定不会对左边的点的答案产生影响。

考虑点A，假设当前点的区间为$[l,r]$，中间点为mid，那么：

  • 如果点A在右区间，那么该区间内它的答案由两部分组成：$[l,mid]$和$[mid+1,rank_A]$，

    前者可以先把$[l,mid]$内元素标记，然后把区间$[l,r]$内的元素以y为第一关键字元素排序后，把标记的元素依次加入维护z的树状数组中，未标记的统计答案，因为标记的元素属于左区间，未标记的属于右区间，只有标记的可能对未标记的有影响。

    后者可以递归处理。

  • 如果点A在左区间，直接递归处理就完了

代码似乎不长：

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
64
65
66
67
68
69
70
71
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 300000
int n,m,xb,head[N],nxt[N],f[N],ans[N],bit[N],cnt[N];
struct point{
	int x,y,z,num,i,ID;
	bool operator < (const point n) const{
		return x<n.x || (x==n.x && y<n.y) || (x==n.x && y==n.y && z<n.z);
	}
	bool operator != (const point n) const{
		return x!=n.x || y!=n.y || z!=n.z;
	}
}a[N],b[N],tmp[N];
bool cmp(point n,point m){
	return n.y<m.y || (n.y==m.y && n.z<m.z) || (n.y==m.y && n.z==m.z && n.x<m.x);
}
void add(int x,int val){
	for (int i=x;i<=m;i+=i&(-i)) bit[i]+=val;
}
int query(int x){
	int sum=0;
	for (int i=x;i;i-=i&(-i)) sum+=bit[i];
	return sum;
}
void cdq(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1,xb1=l,xb2=mid+1;
	sort(b+l,b+r+1,cmp);//不要忘了这个排序哦
	for (int i=l;i<=r;i++){
		if (b[i].ID<=mid) add(b[i].z,b[i].num);
		if (b[i].ID>mid) ans[b[i].ID]+=query(b[i].z);
	}
	for (int i=l;i<=r;i++)
		if (b[i].ID<=mid) add(b[i].z,-b[i].num);
	for (int i=l;i<=r;i++)
		if (b[i].ID<=mid) tmp[xb1++]=b[i];
		else tmp[xb2++]=b[i];
	for (int i=l;i<=r;i++) b[i]=tmp[i];
	cdq(l,mid); cdq(mid+1,r);
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); a[i].i=i;}
	sort(a+1,a+n+1);
	for (int i=1;i<=n;i++)
		if (a[i]!=a[i-1]){b[++xb]=a[i]; head[xb]=a[i].i; b[xb].num=1;}
		else{nxt[a[i].i]=head[xb]; head[xb]=a[i].i; b[xb].num++;}
	sort(b+1,b+xb+1);
	for (int i=1;i<=xb;i++){b[i].ID=i; ans[i]=b[i].num-1;}
	cdq(1,xb);
	
	for (int i=1;i<=xb;i++)
		for (int j=head[i];j;j=nxt[j]) f[j]=ans[i];
	
	for (int i=1;i<=n;i++) cnt[f[i]]++;
	
	for (int i=0;i<n;i++) printf("%d\n",cnt[i]);
	
	return 0;
}