专题：CDQ 分治
本页面将完整介绍 CDQ 分治。
简介
CDQ 分治是一种思想而不是具体的算法，与动态规划类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：
- 解决和点对有关的问题。
- 1D 动态规划的优化与转移。
- 通过 CDQ 分治，将一些动态问题转化为静态问题。
CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。
解决和点对有关的问题
这类问题多数类似于「给定一个长度为 nn 的序列，统计有一些特性的点对 (i,j)(i,j) 的数量/找到一对点 (i,j)(i,j) 使得一些函数的值最大」。
CDQ 分治解决这类问题的算法流程如下：
- 找到这个序列的中点 ；
- 将所有点对 (i,j)(i,j) 划分为 33 类：
- 1≤i≤mid，1≤j≤mid 的点对；
- 1≤i≤mid，mid+1≤j≤n 的点对；
- mid+1≤i≤n，mid+1≤j≤n 的点对。
- 将 (1,n)(1,n) 这个序列拆成两个序列 (1,mid)(1,mid) 和 (mid+1,n)(mid+1,n) 。此时第一类点对和第三类点对都在这两个序列之中；
- 递归地处理这两类点对；
- 设法处理第二类点对。
可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。
在实际应用时，我们通常使用一个函数 solve(l,r) 处理 l≤i≤r，l≤j≤r 的点对。上述算法流 程中的递归部分便是通过 solve(l,mid) 与 solve(mid,r) 来实现的。剩下的第二类点对则需要额外设计算法解决。
典型例题1：LOJ112/洛谷P3810 三维偏序（陌上开花）
分析：
三维偏序（陌上开花）是 CDQ 分治的经典问题。
假设我们现在写好了 solve (l, r) ，并且通过递归搞定了 solve (l, mid) 和 solve(mid+1,r) 。现在我们要做的，就是统计满足 l≤i≤mid，mid+1≤j≤r 的点对 (i, j)(i,j) 中，有多个点对还满足 i<j，ai<aj，bi<bj 的限制条件。
稍微思考一下就会发现，那个 i<j 的限制条件没啥用了：既然 i 比 mid 小， j 比 mid 大，那 i 肯定比 j 要小。 现在还剩下两个限制条件: ai<aj 与 bi<bj , 根据这个限制条件我们就可以枚举 j , 求出有多少个满足条件的 i。
为了方便枚举，我们把 (l,mid) 和 (mid+1,r) 中的点全部按照 a 的值从小到大排个序。之后我们依次枚举每一 个 j , 把所有 ai<aj 的点 i 全部揷入到某种数据结构里（这里我们选择树状数组）。此时只要查询树状数组里有多少个点的 b 值是小于 bj 的，我们就求出了对于这个点 j ，有多少个 ii 可以合法匹配它了。
当我们揷入一个 b 值等于 xx 的点时，我们就令树状数组的 xx 这个位置单点 +1+1，而查询树状数组里有多少个点小于 xx 的操作实际上就是在求前缀和，只要我们事先对于所有的 bb 值做了离散化，我们的复杂度就是对的。
对于每一个 j，我们都需要将所有 ai<aj 的点 i 揷入树状数组中。由于所有的 i 和 j 都已事先按照 aa 值排好序， 这样的话只要以双指针的方式在树状数组里揷入点，则对树状数组的揷入操作就能从 O(n2) 次降到 O(n) 次。
通过这样一个算法流程，我们就用 O(nlogn) 的时间处理完了关于第二类点对的信息了。此时算法的时间复杂度 是 T(n)= T( n/2 ) + T( n/2 ) + O( nlogn )= O(nlog2n)。【三维偏序（陌上开花）-参考代码-CDQ分治】
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,k,m;
struct node
{
int x,y,z,id,w;
bool operator < (const node &A)const{
if(A.x==x && A.y==y) return z < A.z;
else if(A.x==x) return y < A.y;
return x < A.x;
}
}a[N],b[N],d[N];
int ans[N],c[N],cnt[N];
vector <int> v1,v2[N] ;
int lowbit(int x)
{
return x & (-x);
}
void add(int x,int v)
{
for(int i=x;i<N;i+=lowbit(i)) c[i]+=v;
}
int query(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=c[i];
return ans;
}
void cdq(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>1;
cdq(l,mid),cdq(mid+1,r);
int t1=l,t2=mid+1;
for(int i=l;i<=r;i++)
{
if((t1<=mid && a[t1].y<=a[t2].y) || t2>r)
{
add(a[t1].z,a[t1].w);
b[i]=a[t1++];
}
else
{
cnt[a[t2].id]+=query(a[t2].z);
b[i]=a[t2++];
}
}
for(int i=l;i<=mid;i++) add(a[i].z,-a[i].w);
for(int i=l;i<=r;i++) a[i]=b[i];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y>>a[i].z;
a[i].id=i;
}
sort(a+1,a+n+1);
int num=1;
for(int i=2;i<=n+1;i++)
{
if(a[i].x!=a[i-1].x || a[i].y!=a[i-1].y || a[i].z != a[i-1].z)
{
d[++m]=a[i-1];
d[m].w=num;
num=1;
v2[a[i-1].id]=v1;
v1.clear();
}
else
{
num++;
v1.push_back(a[i-1].id) ;
}
}
for(int i=1;i<=m;i++) a[i]=d[i];
cdq(1,m);
for(int i=1;i<=m;i++)
{
int sz=v2[a[i].id].size();
for(auto v:v2[a[i].id]) cnt[v]+=cnt[a[i].id]+sz;
cnt[a[i].id]+=sz;
}
for(int i=1;i<=n;i++) ans[cnt[i]]++;
for(int i=0;i<n;i++) cout<<ans[i]<<'\n';
return 0;
}
CDQ分治的限制
- 题目允许离线操作
- 修改操作对询问的贡献独立，且修改之间互不影响
- 修改对答案的贡献是确定的，与判定标准无关
CDQ分治和整体二分
CDQ分治和整体二分都是基于分治的思想，把复杂的问题拆分成许多可以简单求的解子问题。但是这两种算法必须离线处理，不能解决一些强制在线的题目。不过如果题目允许离线的话，这两种算法要比在线解法（如树套树）快很多。
标签：偏序,int,分治,mid,算法,solve,CDQ From： https://www.cnblogs.com/wenyutao1/p/17770418.html