CDQ用来解决分治时左半部分对右半部分造成影响的问题。
CDQ分治的经典问题是三维偏序问题。
要想解决三维偏序问题，首先你要知道什么是偏序。（废话）
一维偏序：
给出直线上的n个点，问有多少对点满足xi<=xj
对于这个问题，直接排序就可以了。
二维偏序：
给定平面内的n个点，问有多少对点满足xi<=xj且yi<=yj
这是个经典的树状数组问题，相信学过树状数组的人一定都做过·一道叫做数星星的题，这道题就是经典的二维偏序问题，并不需要二维数组，我们可以通过按x坐标为第一关键字排序，从而消除x坐标给答案带来的影响。然后我们用一个树状数组维护前缀和，记录之前有多少点的y坐标比该点小，由于在之前的x坐标一定比较小，因此只要保证y坐标即可。
三维偏序：
给出空间内的n个点，问有多少点对满足xi<=xj且yi<=yj且zi<=zj
树套树？？？码量++，空间++
在不强制在线的情况下，我们完全可以使用CDQ分治这种东西来简化一层树结构，因此三维偏序问题实际上可以这样处理：
1）仿照二位偏序问题，先给x排序，消除其影响。
2）使用CDQ分治，消除y的影响
3）使用数组维护z的前缀，统计答案。
1）、3）都是二维偏序的正常步骤，下面重点来讲讲CDQ分治
前边已经讲过了，CDQ分治要处理左区间对右区间的贡献问题。
其实很简单，我们把每一步操作分成三步：
1）递归处理左区间；2）递归处理右区间；3）处理左区间对右区间的贡献。
在三维偏序问题中，之所以不考虑右区间对左区间的贡献，是因为按x排序了，因此右区间一定不会对左区间造成贡献。
然后我们直接就按y排序，然后看一个东西是在左区间还是右区间，是左区间就放进一个树状数组中，否则直接求贡献。
因为CDQ直接分治到最小的单位，也就是一个点，因此可以保证所有答案都是没有遗漏的。
为了保证答案的不重复性，我们可以在求完贡献后把树状数组内贡献再撤消；
例题：洛谷P3810:陌上花开
参考代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define N 500005
#define lowbit(x) x&-x
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
struct node{int x,y,z,id;}a[N];
bool cmpa(node a,node b)
{
if(a.x!=b.x)return a.x<b.x;
if(a.y!=b.y)return a.y<b.y;
return a.z<b.z;
}
bool cmpb(node a,node b)
{
if(a.y!=b.y)return a.y<b.y;
if(a.x!=b.x)return a.x<b.x;
return a.z<b.z;
}
int n,k,tot,c[],b[],f[],s,j,block[];
void modify(int x,int m){for(;x<=k;x+=lowbit(x))c[x]+=m;}
int query(int x){int res=;for(;x;x-=lowbit(x))res+=c[x];return res;}
void cdq(int l,int r)
{
if(l==r)return;
int mid=(l+r)/;
cdq(l,mid);cdq(mid+,r);
sort(a+l,a+r+,cmpb);
for(int i=l;i<=r;i++)(a[i].x<=mid)?modify(a[i].z,),s=:b[a[i].id]+=query(a[i].z);
for(int i=l;i<=r;i++)if(a[i].x<=mid)modify(a[i].z,-);
}
int main()
{
ios::sync_with_stdio();cin.tie();cout.tie();
cin>>n>>k;//n=read();k=read();
for(int i=;i<=n;i++)
{
cin>>a[i].x>>a[i].y>>a[i].z;//=read();a[i].y=read();a[i].z=read();
a[i].id=i;
}
sort(a+,a++n,cmpa);
for(int i=;i<=n;)
{
j=i+;
while(j<=n&&a[i].x==a[j].x&&a[i].y==a[j].y&&a[i].z==a[j].z)j++;
while(i<j)block[a[i].id]=a[j-].id,i++;
}
for(int i=;i<=n;i++)a[i].x=i;
cdq(,n);
for(int i=;i<=n;i++)f[b[block[a[i].id]]]++;
for(int i=;i<n;i++)printf("%d\n",f[i]);
return ;
}
三位偏序模板代码