我们考虑一个三维偏序问题：
即(i,j)满足ai<aj bi<bj ci<cj。
最暴力的做法是n^2的。
我们可以将第一维排序，然后用二维树状数组来记录bi,ci，这样可以做到n*log(n)的时间复杂度，但是当bi,ci数字很大时不能用二维树状数组记录时怎么办呢？
我们可以用树套树，但树套树不好写，这时我们有一种方法可以解决这个问题。
CDQ分治：
我们先将ai排序
然后类似于整体二分的思想进行分治
我们将数组分成[l,mid],[mid+1][r]两个区间，对于两个区间
我们将左一半和右一半分别以bi排序，这时我们枚举两个区间
设左边的区间当前访问的是i，右边当前访问的是j
则我们可以发现若b[i]<b[j]则b[i]<b[j+1]
所以我们可以用线性的时间来解决bi<bj的问题
那么zi<zj呢，我们可以用树状数组来维护。
这样的时间复杂度是T(n)=2T(n/2)+O(n*logn)
即T(n)=O(n*logn*logn)。
但是其实分别排序左右两个序列是不必要的，因为在递归完当前层时左右两个区间是分别bi有序的，所以我们可以用归并排序来做。
下面是一道例题：
BZOJ3262: 陌上花开
Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
Output
包含N行，分别表示评级为0…N-1的每级花的数量。
Sample Input
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
Sample Output
3
1
3
0
1
0
1
0
0
1
1
3
0
1
0
1
0
0
1
HINT
1 <= N <= 100,000, 1 <= K <= 200,000
Source
树套树 CDQ分治
Solution
要注意此题是可以等于的。
这里给出的代码是分别排序左右两边的代码。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,K,f[200100],p[100100]; struct node1{int x,y,z,num,tot;}a[100100]; struct node{int x,y,z,t,ans;}A[100100]; bool cmp(node1 a,node1 b) { if (a.x==b.x&&a.y==b.y) return a.z<b.z; if (a.x==b.x) return a.y<b.y; return a.x<b.x; } bool cmp1(node a,node b) { return a.y<b.y;} int lowbit(int x) { return x&(-x);} int get(int x) { int ans=0; for (int i=x;i>=1;i-=lowbit(i)) ans+=f[i]; return ans; } void add(int x,int y) { for (int i=x;i<=K;i+=lowbit(i)) f[i]+=y; } void erfen(int l,int r) { if (l==r) return; int mid=(l+r)/2; erfen(l,mid);erfen(mid+1,r); sort(A+l,A+mid+1,cmp1);sort(A+mid+1,A+r+1,cmp1); int i=l,j=mid+1; while (j<=r) { while (i<=mid&&A[i].y<=A[j].y) add(A[i].z,A[i].t),i++; A[j].ans+=get(A[j].z); j++; } for (int k=l;k<=i-1;k++) add(A[k].z,-A[k].t); } int main() { scanf("%d%d",&n,&K); for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z),a[i].num=i; sort(a+1,a+n+1,cmp); int tot=1,num=0; a[1].tot=1; for (int i=2;i<=n+1;i++) if (i==n+1||a[i].x!=a[i-1].x||a[i].y!=a[i-1].y||a[i].z!=a[i-1].z) { A[++num].x=a[i-1].x;A[num].y=a[i-1].y;A[num].z=a[i-1].z; A[num].t=tot; tot=1; a[i-1].tot=num; }else tot++,a[i].tot=num+1; erfen(1,num); for (int i=1;i<=num;i++) p[A[i].ans+A[i].t-1]+=A[i].t; for (int i=0;i<n;i++) printf("%d\n",p[i]); return 0; } |
下面是用归并排序的代码：
lxy说道： 