CDQ 分治，据说是由陈丹琦最先引入国内 OI 圈的。它与 dp 类似，是一种思想，而不是一种具体的算法。
CDQ 分治一般用来解决点对的问题，例如P3810 【模板】三维偏序（陌上花开）这道题：
给定 n 个元素，每个元素有权值 a_i,b_i,c_i。
规定 f(i) 为满足 a_j<=a_i,b_j<=b_i,c_j<=c_i 且 j!=i 的 j 的个数。
求所有 0<=x<n 的 ans(x) 表示有多少个满足 f(i)=x 的 i。
CDQ 分治的步骤大体如下：
-
二分一个
-
递归处理所有 的点对和所有 的点对
-
设法处理所有 的点对
没错，归并排序求逆序对也是类似的思路，所以可以说归并排序求逆序对也是一种 CDQ 分治（
回到例题，首先考虑一个弱智版问题：
每个元素只有一个属性 a_i
很明显排一次序就行了。
再来看一个难一点的
每个元素有两个属性 a_i 和 b_i
可以先按 排序，然后再用树状数组计算贡献。
sort(a+1,a+n+1,cmpa); // 按 a_i 排序
for(int i=1;i<=n;i++)
{
// 下文 add 函数和 que 函数分别是树状数组的单点修改和前缀和查询
a[i].ans=que(a[i].b); // 查询
add(a[i].b,1); // 插入树状数组
}
回到例题，首先对 排序，这样我们就消去了一个关键字。由于有重复的元素，所以我们可以做一下去重（其实不去重也没什么关系）。
接下来，我们可以使用 CDQ 分治来再去一个关键字。
具体的做法是，递归分治完两边后，需要计算 对 的贡献，那么由于 ，所以可以先对两个区间的 排序，然后用树状数组统计答案。
排序部分可以用归并排序，省去一些时间。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
struct node
{
int a,b,c,cnt,ans;
}a[100005],tmp[100005];
int n,k;
int c[200005],ans[100005];
inline bool cmpa(node x,node y)
{
if(x.a==y.a)
{
if(x.b==y.b)
{
return x.c<y.c;
}
return x.b<y.b;
}
return x.a<y.a;
}
inline bool cmpb(node x,node y)
{
if(x.b==y.b)
{
return x.c<y.c;
}
return x.b<y.b;
}
inline void add(int pos,int val)
{
for(int i=pos;i<=k;i+=i&-i)
{
c[i]+=val;
}
}
inline int que(int pos)
{
int res=0;
for(int i=pos;i>=1;i-=i&-i)
{
res+=c[i];
}
return res;
}
void slove(int l,int r)
{
// “分”
if(l==r)
{
return;
}
int mid=l+r>>1;
slove(l,mid);
slove(mid+1,r);
// “治”
int j=l,tot=0;
for(int i=mid+1;i<=r;i++) // 归并排序，计算贡献
{
while(j<=mid&&a[j].b<=a[i].b)
{
add(a[j].c,a[j].cnt);
tmp[++tot]=a[j++];
}
a[i].ans+=que(a[i].c);
tmp[++tot]=a[i];
}
while(j<=mid)
{
add(a[j].c,a[j].cnt);
tmp[++tot]=a[j++];
}
for(int i=l;i<=mid;i++) // 清空树状数组，这样写比 memset 快一点（
{
add(a[i].c,-a[i].cnt);
}
for(int i=l;i<=r;i++)
{
a[i]=tmp[i-l+1];
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
}
sort(a+1,a+n+1,cmpa);
int tot=0;
for(int i=1,sum=0;i<=n;i++) // 去重
{
sum++;
if(a[i].a!=a[i+1].a||a[i].b!=a[i+1].b||a[i].c!=a[i+1].c)
{
a[++tot]=a[i];
a[tot].cnt=sum;
sum=0;
}
}
slove(1,tot);
for(int i=1;i<=tot;i++)
{
ans[a[i].ans+a[i].cnt-1]+=a[i].cnt; // 计算答案，<= a_i 的有 a_i.ans 个，再算上 = a_i 的，最后减去重复计算的 a_i
}
for(int i=0;i<n;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
做完这道题，可以发现 CDQ 分治处理偏序问题的本质是消关键字（
所以四维偏序可以使用 CDQ 分治套 CDQ 分治来做（（（