算法简介
CDQ 分治是一种基于分治思想，因原理与写法的不同，大概可以分为三类：
- 解决有关点对的问题
- 1D 动态规划的优化与转移
- 将动态问题转成静态问题
解决有关点对的问题
\(\quad\)这类问题多数类似于：给定一个长度为 n 的序列，统计有一些特性的点对 的数量/找到一对点 使得一些函数的值最大。而用 CDQ 分治解决这类问题的算法流程大致如下：
- 找到这个序列的中点 mid
- 将所有点对 \((i,j)\) 分成 3 类：
- 将 \((1,n)\) 这个序列拆成两个序列 \((1,mid)\) 和 \((mid+1,n)\)。此时第一类点对和第三类点对都在这两个序列中
- 递归处理这两类点对
- 设法处理第二类点对
可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间，
例题
\(\quad\)这是 CDQ 分治的一个很经典的应用，对于一个区间，先处理左区间和右区间的贡献，然后想办法处理第二类情况。首先按 c 排序，我们会发现 \(c_i<c_j\) 这个限制已经没有用了。然后我们对于每一个右区间的 j ，求出有多少个左区间的 i 满足条件。这里我们可以先将两个区间的 a 按照从小到大的顺序排个序，然后用两个指针，按顺序对于每一个 j 将 a 比自己小的 i 的 b 插入树状数组中，然后查询就直接在树状数组里面查询即可。
时间复杂度：\(O(nlogn^2)\)
code:
//code by SPzos
#include<bits/stdc++.h>
#define ll long long
#define double
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define fd(i,j,k) for(register int i=j;i>=k;--i)
#define ff(i,x) for(register int i=head[x];i;i=e[i].nxt)
#define fv(i,x) for(register int i=0;i<v[x].size();++i)
using namespace std;
const int N=100010,K=200010;
inline int read(){
int ret=0,f=0;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();}
while(ch>='0' && ch<='9') {ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();}
return f?-ret:ret;
}
struct node{
int x,y,z,ans,w;
}a[N],b[N];
bool cmp1(node p1,node p2){
if(p1.x==p2.x){
if(p1.y==p2.y) return p1.z<p2.z;
return p1.y<p2.y;
}
return p1.x<p2.x;
}
bool cmp2(node p1,node p2){
if(p1.y==p2.y) return p1.z<p2.z;
return p1.y<p2.y;
}
struct tree{
int kk,c[K];
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x,int y){
for(int i=x;i<=kk;i+=lowbit(i)) c[i]+=y;
}
inline int query(int x){
int sum=0;
for(int i=x;i>0;i-=lowbit(i)) sum+=c[i];
return sum;
}
}t;
inline void cdq(int l,int r){
if(l==r) return ;
int m=l+r>>1;
cdq(l,m);cdq(m+1,r);
sort(a+l,a+m+1,cmp2);
sort(a+m+1,a+r+1,cmp2);
int t1=l,t2=m+1;
while(t2<=r){
while(a[t1].y<=a[t2].y && t1<=m){
t.add(a[t1].z,a[t1].w);
++t1;
}
a[t2].ans+=t.query(a[t2].z);
++t2;
}
fo(i,l,t1-1) t.add(a[i].z,-a[i].w);
}
int ct,cnt[N],n,k;
int main(){
n=read();k=read();
t.kk=k;
fo(i,1,n){
b[i].x=read();b[i].y=read();b[i].z=read();
}
sort(b+1,b+1+n,cmp1);
int c=0;
fo(i,1,n){
c++;
if(b[i].x!=b[i+1].x || b[i].y!=b[i+1].y || b[i].z!=b[i+1].z){
a[++ct]=b[i];
a[ct].w=c;c=0;
}
}
cdq(1,ct);
fo(i,1,ct) cnt[a[i].ans+a[i].w-1]+=a[i].w;
fo(i,0,n-1) printf("%dn",cnt[i]);
return 0;
}
\(\quad\)扩展：既然说到了三位偏序，那就顺便提一下 四维偏序。
\(\quad\)四维偏序就是 CDQ分治 套 CDQ分治。
\(\quad\)假如四维偏序的元素属性是 a,b,c,d，那么先按 a 排序，然后处理一个区间的时候，还是递归处理左右区间，至于左区间对右区间的贡献，就需要再套一个 CDQ 分治来操作。具体就是对于左区间的数字打上一个标记 L ，右区间打上一个 标记 R ，然后新的 CDQ2 分治的基础是 b 已经排好序了，先忽略 a 这一维，那么就是一个三维偏序，至于 a 的限制就是当 j 的标记是 R，且 i 的标记是 L 的时候，才能累计贡献。
\(\quad\)我们可以换一个角度，求出每一次删除后会影响多少个逆序对。首先还是要按时间排序，这样每个点就只用在自己前面找就可以了，可以保证不重不漏。但是有些已经删除的就不能算在贡献里面，那我们就可以给它打一个负标记，这样就会和之前的正标记抵消了。然后计算答案的话，就可以对每一个点存一下它们消除的时间，最后求一个前缀和就行了。
//code by SPzos
#include<bits/stdc++.h>
#define ll long long
#define double
#define fo(i,j,k) for(register int i=j;i<=k;++i)
#define fd(i,j,k) for(register int i=j;i>=k;--i)
#define ff(i,x) for(register int i=head[x];i;i=e[i].nxt)
#define fv(i,x) for(register int i=0;i<v[x].size();++i)
using namespace std;
const int N=100010;
inline int read(){
int ret=0,f=0;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=1;ch=getchar();}
while(ch>='0' && ch<='9') {ret=(ret<<1)+(ret<<3)+ch-(1<<4)-(1<<5);ch=getchar();}
return f?-ret:ret;
}
int tot,n,m,a[N];
ll ans[N];
int pos[N],c[N];
struct AC{
int m,v,d,id,t;//正负，数值，位置，t->time
}e[N<<1];
bool cmp1(AC x,AC y){return x.d<y.d;}
void add(int x,int k){while(x<=n) c[x]+=k,x+=(x&(-x));}
int query(int x){int sum=0;while(x) sum+=c[x],x-=(x&(-x));return sum;}
void cdq(int l,int r){
if(l==r) return ;
int mid=l+r>>1;
int j=l;
cdq(l,mid);cdq(mid+1,r);
sort(e+l,e+mid+1,cmp1);
sort(e+mid+1,e+r+1,cmp1);
for(int i=mid+1;i<=r;++i){
while(j<=mid && e[j].d<=e[i].d) add(e[j].v,e[j].m),++j;
ans[e[i].id]+=e[i].m*(query(n)-query(e[i].v));
}
for(int i=l;i<j;++i) add(e[i].v,-e[i].m);
j=mid;
for(int i=r;i>mid;--i){
while(j>=l && e[j].d>=e[i].d) add(e[j].v,e[j].m),--j;
ans[e[i].id]+=e[i].m*query(e[i].v-1);
}
for(int i=mid;i>j;--i) add(e[i].v,-e[i].m);
}
int main(){
n=read();m=read();
fo(i,1,n) a[i]=read(),pos[a[i]]=i,e[++tot]=(AC){1,a[i],i,0,tot};
for(int i=1,x;i<=m;++i) x=read(),e[++tot]=(AC){-1,x,pos[x],i,tot};
cdq(1,tot);
fo(i,1,m) ans[i]+=ans[i-1];
for(int i=0;i<m;++i) printf("%lldn",ans[i]);
return 0;
}
CDQ 分治优化 1D/1D 动态规划的转移
$\quad$1D/1D 动态规划指的是一类特定的 DP 问题，该类题目的特征是 DP 数组是一维的，转移是 \(O(n^2)\) 的，而我们希望能用 CDQ 分治的思想将其优化成 \(O(nlogn^2)\)。
\(\quad\)例如给定一个序列，每一个元素有两个属性 a,b 。我们希望计算一个式子的值，转移方程如下：
\[dp_i=1+max_{j=1}^{i-1}dp[j][a_j<a_i][b_j<b_i] \]\(\quad\)这是一个二维最长上升子序列的 DP 方程。
\(\quad\)其实优化步骤也是差不多的：
- 处理左区间
- 处理左区间对右区间的影响
- 处理右区间
\(\quad\)这里的第 2 步在之前的问题中什么时候都可以操作，但是在此必须”夹在中间“，这是显然的。
例题
\(\quad\)很明显是个二维最长上升子序列问题，所以可以考虑用 CDQ 分治优化。
\(\quad\)我们需要记录四个数组
f1[i]//以i为结尾的最长长度
f2[i]//以i为开头的最长长度
g1[i]//以i为结尾的最长长度的数量
g2[i]//以i为开头的最长长度的数量
\(\quad\)这个就可以用 CDQ 分治直接求，第二个步骤的数据结构既要支持单点修改，还要支持查询区间最大值和对应的数量，个人认为线段树是一个很好的选择。然后考虑每一个点能在几个这种序列上。不可能去记录路径的，但是我们可以发现一个性质就是当一个的点的 \(f1[i]+f2[i]-1=len_{max}\) 时，它出现在最长序列的次数就是 \(g1[i]\times g2[i]\) ，这是显然的。而总的数量可以算出来，假设是 sum ，那么概率就是 \(\frac{g1[i]\times g2[i]}{sum}\) ，此题终。
\(\quad\)注意：这个题开 long long 都不够，要开 double ，听说不会爆，原理未知......
将动态问题转化为静态问题
\(\quad\)前两种问题是将序列折半后递归处理点对间的关系，不过在这一节中折叠的是时间序列。
\(\quad\)它适用于一些$\lceil $ 需要支持做...修改然后询问...\(\rceil\) 的数据结构题。该类题目有两个特点：
- 如果将操作离线，所有操作会按照时间自然的排成一个序列。
- 每一个修改均与之后的询问操作息息相关。
\(\quad\)我们可以使用 CDQ 分治对这个操作序列进行分治，先递归处理 \((l,mid)\) 的修改-询问关系，再处理所有 \(l\leq i \leq mid,mid+1\leq j\leq r\) 的修改-询问关系，其中 i 是一个修改，j 是一个询问，最后再处理 \((mid+1,r)\) 的修改-询问关系。注意，如果修改之间是独立的，那么就不需要管这个处理的顺序了。
\(\quad\)想一个很经典的例子：动态二维数点。
\(\quad\)只用考虑在自己之前的操作对自己的贡献，这就可以将这个问题转化为静态问题，用 CDQ 去解决。
\(\quad\)因为这一点，CDQ 分治被称为 \(\lceil\) 动态问题转化为静态问题的工具\(\rceil\)。
例题
注意
\(\quad\)在我之前的程序中都是直接在递归中 sort ，事实上这样跑的复杂度假了，但是也能跑过去，所以如果打代码的时候有空闲时间其实可以以归并排序这种思想来处理左右区间的同时排序，这样的复杂度就比较正确。但是有点复杂，sort 确实比较直观。