CDQ分治常用于解决多维偏序关系问题，以三维为例，第一维可以排序解决，第二维进行分治，第三位常用数据结构（树状数组）维护，于是也可以将动态带修改问题，离线处理，常默认时间为第一维。
由于许多时候同一个操作要分成多个操作来解决，所以要格外注意结构体数组的大小是否恰当，同时留意树状数组的边界。
CDQ优化dp时，通常是应用于1D/1Ddp问题，即dp数组是一维的，转移是1维的，可以从O(N2)优化到O(N*log2(N)2)，分治时，若l=r则直接更新dp[l]，否则先递归(l,mid)，之后处理所有的l<=i<=mid对于mid+1<=j<=r的贡献，再递归(mid+1,r)
求sum(i=1->n)(sum(j=1->n))max(v[i],v[j])|x[i]-x[j]|.首先按照v升序排序，考虑左区间对右区间的贡献，设i<j，绝对值分为x[i]<x[j]和x[i]>x[j]，按照x升序排序，找到第一个x[i]>x[j]的位置，j到左区间的v就是v[j]，距离和就是j坐标坐标小于j的数的个数-坐标小于j的数的坐标和+坐标大于j的数的距离和-j坐标*坐标大于j的数的个数。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1,a=0,b=0;
for(int i=l;i<=mid;i++)a+=q[i].y;
for(;j<=r;j++){
for(;i<=mid&&q[i].y<q[j].y;i++){
a-=q[i].y;
b+=q[i].y;
}
ans+=q[j].x*((i-l)*q[j].y-b+a-(mid-i+1)*q[j].y);
}
merge(q+l,q+mid+1,q+mid+1,q+1+r,pre+l,[](node a,node b){return a.y<b.y;});
for(int i=l;i<=r;i++)q[i]=pre[i];
}
求有多少个连续子序列满足其和>=L且<=R.序列是连续的，可会议进行CDQ分治，满足限制l和r的下标连续递增，类加成前缀和，注意也要加入sum[0]。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int h=l,t=l-1;
for(int i=mid+1;i<=r;i++){
while(t+1<=mid&&s[i]-s[t+1]>=liml)t++;/*找到第一个不合法的*/
while(h<=mid&&s[i]-s[h]>limr)h++;/*找到第一个合法的*/
ans+=t-h+1;
}
sort(s+l,s+r+1);
}
求一个序列有多少连续子序列满足平均值>=k.有平均值，则首先将序列所有值减去k，之后判断区间和即可，注意sum[0]也要计入。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1,sum=0;
for(;j<=r;j++){
for(;i<=mid&&s[j]-s[i]>=0;i++)sum++;
ans+=sum;
}
sort(s+l,s+r+1);
}
一棵树，有两种点权a和b，以1为根，问每个点的子树内a和b权值均小于该点的点的数量。前两维两种点权偏序，第三维dfs序偏序，大的优先，这样就优先子树。
struct Ask{
int red,blue,ipt,opt,id;
inline bool friend operator<(Ask a,Ask b){
return a.red==b.red?a.blue==b.blue?a.ipt>b.ipt:a.blue<b.blue:a.red<b.red;
}
}q[N],pre[N];
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1;
for(;j<=r;j++){
for(;i<=mid&&q[i].blue<=q[j].blue;i++)bit.add(q[i].ipt,1);
ans[q[j].id]+=bit.ask(q[j].ipt,q[j].opt);
}
for(--i;i>=l;i--)bit.add(q[i].ipt,-1);
merge(q+l,q+1+mid,q+1+mid,q+1+r,pre+l,[](Ask a,Ask b){return a.blue==b.blue?a.ipt>b.ipt:a.blue<b.blue;});
for(int i=l;i<=r;i++)q[i]=pre[i];
}
有n个元素，每个元素有a,b,c三种属性，f(i)为a[j]<=a[i]&&b[j]<=b[i]&&c[j]<=c[i]的j的数量，求f(i)=d的数量，d属于0到n-1.三维分别是x,y,z，注意需要去重，树状数组的范围是z的范围，由于CDQ时还会对第二维进行排序，所以需要在结构体内部记录ans，这样排序是才会跟着该改变，而不能用单纯一个数组来记录。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1;
for(;j<=r;j++){
for(;i<=mid&&q[i].y<=q[j].y;i++)bit.add(q[i].z,q[i].w);
q[j].ans+=bit.query(q[j].z);
}
for(--i;i>=l;i--)bit.add(q[i].z,-q[i].w);
merge(q+l,q+mid+1,q+mid+1,q+1+r,pre+l,[](Ask a,Ask b){return a.y<b.y;});
for(int i=l;i<=r;i++)q[i]=pre[i];
}
for(int i=1;i<=n;i++){
col++;
if(q[i].x!=q[i+1].x||q[i].y!=q[i+1].y||q[i].z!=q[i+1].z)q[++m]=q[i],q[m].w=col,col=0;
}
CDQ(1,m);
for(int i=1;i<=m;i++)ans[q[i].ans+q[i].w-1]+=q[i].w;
for(int i=0;i<n;i++)cout<<ans[i]<<'\n';
维护一个支持单点修改和查询矩阵和的矩阵。对于一个数会对(1,1)到(x,y)做出贡献当且仅当横纵坐标和出现时间都小于当前询问，将询问差分，注意所欲坐标要+1来防止0.
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
CDQ(mid+1,r);
int i=l,j=mid+1;
for(;j<=r;j++){
for(;i<=mid&&a[i].x<=a[j].x;i++)if(a[i].ask==0)bit.add(a[i].y,a[i].w);
if(a[j].ask==1)a[j].w+=bit.query(a[j].y);
}
for(--i;i>=l;i--)if(a[i].ask==0) bit.add(a[i].y,-a[i].w);
merge(a+l,a+mid+1,a+mid+1,a+r+1,preask+l);
for(i=l;i<=r;i++)a[i]=preask[i];
}
while(opt!=3){
if(opt==1){
int x,y,v;cin>>x>>y>>v;
x++,y++;
a[++cnt]={cnt,x,y,v,0};
}
else{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;x2++,y2++;
a[++cnt]={cnt,x1,y1,0,1};
a[++cnt]={cnt,x2,y2,0,1};
a[++cnt]={cnt,x2,y1,0,1};
a[++cnt]={cnt,x1,y2,0,1};
}
cin>>opt;
}
for(int i=1;i<=cnt;i++)if(a[i].ask==1)cout<<a[i].w+a[i+1].w-a[i+2].w-a[i+3].w<<'\n',i+=3;
单点标记，每次询问到距离询问最近的标记点的距离，距离为曼哈顿距离。考虑去掉曼哈顿距离的绝对值，设询问i，dis(i,j)=|x[i]-x[j]|+}y[i]-y[j]|，假设j在i的左下方，当x[j]+y[j]最大时dis最小，再满足时间轴要求即为三维偏序，四次CDQ，每次对应一个方向，都等效成查找距离当前点最近的左下方的点，maxx-x相当于左右翻转（查找右下），maxy-y相当于上下翻转（查找左上），两者同时做即查找右上，查询|x1-x2|+|y1-y2|，翻转后等效成查询(x1+y1)-(x2+y2)，于是可以将x+y作为整体用树状数组维护最大值。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid),CDQ(mid+1,r);
int i=l,j=mid+1;
for(;j<=r;j++)
if(!a[j].ask){
for(;a[i].x<=a[j].x&&i<=mid;i++)
if(a[i].ask)bit.add(a[i].y,a[i].x+a[i].y);
int t=bit.query(a[j].y);
if(t)ans[a[j].tim]=min(ans[a[j].tim],a[j].x+a[j].y-t);
}
for(j=l;j<i;j++)if(a[j].ask)bit.clear(a[j].y);
merge(a+l,a+mid+1,a+mid+1,a+r+1,q+l);
for(i=l;i<=r;i++)a[i]=q[i];
}
inline void del(){
rx=ry=m=0;
for(int i=1;i<=n;i++)if(!a[i].ask)rx=max(rx,a[i].x),ry=max(ry,a[i].y);
for(int i=1;i<=n;i++)if(a[i].x<=rx&&a[i].y<=ry)q[++m]=a[i];
for(int i=1;i<=m;i++)a[i]=q[i];
}
for(int i=1;i<=n;i++)p[i]=a[i];
del();CDQ(1,m);
for(int i=1;i<=n;i++)a[i]=p[i],a[i].x=lx-a[i].x;
del();CDQ(1,m);
for(int i=1;i<=n;i++)a[i]=p[i],a[i].y=ly-a[i].y;
del();CDQ(1,m);
for(int i=1;i<=n;i++)a[i]=p[i],a[i].x=lx-a[i].x,a[i].y=ly-a[i].y;
del();CDQ(1,m);
对一个排列，按照某种顺序依次删除m个元素，求每次删除之前的逆序对数。分成两部分考虑，tim[i]<tim[j]&&pos[i]<pos[j]&&v[i]>v[j]或tim[i]<tim[j]&&pos[i]>pos[j]&&v[i]<v[j]，之后可以进行分治，再前缀和累加。
void CDQ(int l,int r){
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid),CDQ(mid+1,r);
int i=l,j=mid+1;
for(;j<=r;j++){
for(;a[i].x<=a[j].x&&i<=mid;i++)bit.add(a[i].y,a[i].flag);
ans[a[j].id]+=a[j].flag*bit.ask(a[j].y+1,n);
}
for(j=l;j<i;j++)bit.add(a[j].y,-a[j].flag);
i=mid,j=r;
for(;j>mid;j--){
for(;a[i].x>=a[j].x&&i>=l;i--)bit.add(a[i].y,a[i].flag);
ans[a[j].id]+=a[j].flag*bit.query(a[j].y-1);
}
for(j=i+1;j<=mid;j++)bit.add(a[j].y,-a[j].flag);
merge(a+l,a+mid+1,a+mid+1,a+r+1,preask+l,cmp0);
for(i=l;i<=r;i++)a[i]=preask[i];
}
for(int i=1;i<=n;i++)cin>>b[i],pos[b[i]]=i,a[++cnt]={cnt,i,b[i],1,1,0};
for(int i=1,x;i<=m;i++)cin>>x,a[++cnt]={cnt,pos[x],x,-1,-1,i};
for(int i=1;i<=cnt;i++)preask[i]=a[i];
CDQ(1,cnt);
for(int i=1;i<=m;i++)ans[i]+=ans[i-1];
for(int i=0;i<m;i++)cout<<ans[i]<<'\n';
一个序列，有的数可能会发生变化，但是同一时刻最多只有一个数发生变化，求一个子序列使得任意变化都是不降的。CDQ分治优化dp，对于x<y，当且仅当val[x]<=mi[y]&&ma[x]<=val[y]时可以满足题目要求（修改没有继承），CDQ时先将左区间按最大值升序排序，再将右区间按val升序排序，之后维护，最后再复原打乱的原数组（按pos升序排序）。
void CDQ(int l,int r){
if(l==r)return f[l]=max(f[l],1),void();
int mid=l+r>>1;
CDQ(l,mid);
sort(a+l,a+mid+1,[](node a,node b){return a.ma<b.ma;});
sort(a+mid+1,a+r+1,[](node a,node b){return a.val<b.val;});
int i=l,j=mid+1;
for(;j<=r;j++){
for(;a[i].ma<=a[j].val&&i<=mid;i++)bit.add(a[i].val,f[a[i].pos]);
f[a[j].pos]=max(f[a[j].pos],bit.ask(a[j].mi)+1);
}
while(i>l)bit.clear(a[--i].val);
sort(a+mid+1,a+r+1,[](node a,node b){return a.pos<b.pos;});
CDQ(mid+1,r);
}