CDQ分治是一种神奇的分治算法
它的核心思想大致是这样的
将所有的操作看成一个区间
一个[L,R]的区间分为[L,mid][mid+1,R]这两个子问题
然后处理[L,mid]这个区间对[mid+1,R]这个区间的贡献
这样讲解十分抽象，我们还是来看几个实际问题
二维偏序问题：
给定N个有序对(a,b)，求对于每个(a,b)，满足a2<a且b2<b的有序对(a2,b2)有多少个
我们现将所有点排序按一维，这样右区间就不会对左区间产生影响，就可以CDQ了
在具体处理左边区间对右边影响时，
我们将[L,mid]和[mid+1,R]再分别按另一维排序
然后用两个指针扫一下，就好了
我们设想一下将二维的偏序加到三维：
其实做法是差不多的
一维排序，一维CDQ一维树状数组
具体处理时我们将[L,min],[mid+1,R]排序后用两个指针扫时
遇到左边小于右边的情况就将树状数组在a[i].z处加上1
然后在j处的答案就是sum(a[j].z)
上代码（洛谷3810）
# include<iostream> # include<cstdio> # include<algorithm> # include<cmath> # include<cstring> using std::sort; inline int read() { int x=0; char ch=getchar(); while(ch>'9' || ch<'0') ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } const int mn = 100005; struct element{ int x,y,z,s,ans; }; element a[mn],b[mn]; int tot,ans[mn]; bool cmp1(element m,element n)//按x排序 { if(m.x==n.x && m.y==n.y) return m.z<n.z; else if(m.x==n.x) return m.y<n.y; else return m.x<n.x; } bool cmp2(element m,element n)//按y排序 { if(m.y==n.y) return m.z<n.z; return m.y<n.y; } int n,k; struct BIT{ int siz,tr[mn*2]; void add(int i,int x) { for(i;i<=siz;i+=(i&-i)) tr[i]+=x; } int sum(int i) { int ret=0; for(i;i;i-=(i&-i)) ret+=tr[i]; return ret; } }T; void CDQ(int l,int r) { if(l==r) return ; int mid=l+r>>1; CDQ(l,mid); CDQ(mid+1,r); sort(b+l,b+mid+1,cmp2); sort(b+mid+1,b+r+1,cmp2); int i=l,j=mid+1; while(j<=r) { while(i<=mid && b[i].y<=b[j].y) { T.add(b[i].z,b[i].s); i++; } b[j].ans+=T.sum(b[j].z); j++; } for(int s=l;s<i;s++) T.add(b[s].z,-b[s].s); } int main() { n=read(),k=read(); T.siz=k; for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read(); sort(a+1,a+1+n,cmp1); int cnt=0; for(int i=1;i<=n;i++) { cnt++; if(a[i].x!=a[i+1].x || a[i].y!=a[i+1].y || a[i].z!=a[i+1].z) { b[++tot]=a[i]; b[tot].s=cnt; cnt=0; } } CDQ(1,tot); /*for(int i=1;i<=tot;i++) printf("%d ",b[i].ans); printf(" ");*/ for(int i=1;i<=tot;i++) ans[b[i].ans+b[i].s-1]+=b[i].s; for(int i=0;i<n;i++) printf("%d ",ans[i]); return 0; }
（未完待更）