浅谈 CDQ 分治

· · 算法·理论

本文章同步发表在博客园。

CDQ 好强，拜谢 CDQ /bx

CDQ 是我教练的学姐喵！

什么是 CDQ 分治？

CDQ 分治一般用于求解偏序问题，二维偏序问题一般可以不使用 CDQ 分治而用普通分治或树状数组轻松解决，三维偏序问题 CDQ 分治是最佳选择，而四维偏序问题就需要 CDQ 套 CDQ 了。

CDQ 分治求解三维偏序问题时类似于是把用来求解二维偏序的两种方案（归并排序和树状数组）结合在一起使用，外层是一个归并排序的分治，内层处理时再套上树状数组，就能解决三维偏序问题了。

CDQ 分治模板题

模板，三维偏序。

那我就借这道题来详解一下 CDQ 分治吧。

首先执行普通的读入，然后排序并离散化。

离散化完成之后，需保证其按照 a 升序排序。

接下来步入 CDQ 分治的核心环节。

首先递归处理左右两边。

重点来了！

这里是一个类似于求逆序对的时候所运用的双指针，用 p1 和 p2 两个指针分别代表左右两个子区间。

接下来开始判断。

如果 p1 的 b 小于等于 p2 的 b，那么这个时候可不是像二维偏序那样直接开始统计答案，而是把 p1 的 c 值存进树状数组！因为到时候还需要判断最后一维 c，因此不能在 b 满足条件时就草草记录。

否则的话，也就是说 p1 的 b 比 p2 的 b 要大，那么借助树状数组当前存储的东西，将 p2 所对应的答案加上当前树状数组中存储的小于等于 p2 的 c 的个数。

执行完这一块操作，CDQ 分治的精华就已经结束了。它不同于普通的二维偏序问题，在满足条件的情况下就直接开始记录，而是把剩下那一维塞进树状数组，需要的时候再取出来并统计。

然后清空一下树状数组并把原数组的这个区间以 b 为第一关键字排好序即可。

最后根据题目要求计算一下答案就结束啦。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5 , K = 2e5+5;
struct node{
    int x,y,z,t,ans;
}s[N],a[N],tmp[N];
int m,n,ppp,c[K],cnt[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp1(node d1,node d2){
    if(d1.x!=d2.x)return d1.x<d2.x;
    return (d1.y<d2.y||(d1.y==d2.y&&d1.z<d2.z));
}
bool cmp2(node d1,node d2){
    return (d1.y<d2.y||(d1.y==d2.y&&d1.z<d2.z));
}
void add(int x,int k){while(x<=ppp)c[x]+=k,x+=x&-x;return;}
int ask(int x){int sum=0;while(x)sum+=c[x],x-=x&-x;return sum;}
void CDQsolve(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQsolve(l,mid),CDQsolve(mid+1,r);
    int p1=l,p2=mid+1;
    for(int i=l;i<=r;i++)
        if(p2>r||(p1<=mid&&a[p1].y<=a[p2].y))
            tmp[i]=a[p1],add(a[p1].z,a[p1].t),++p1;
        else tmp[i]=a[p2],tmp[i].ans+=ask(a[p2].z),++p2;
    for(int i=l;i<=mid;i++)add(a[i].z,-a[i].t);
    for(int i=l;i<=r;i++)a[i]=tmp[i],tmp[i]={0,0,0,0,0};return;
}
int main(){
    m=read(),ppp=read();
    for(int i=1;i<=m;i++)s[i].x=read(),s[i].y=read(),s[i].z=read();
    sort(s+1,s+m+1,cmp1);
    for(int i=1;i<=m;a[n].t++,i++)
        if(s[i].x!=s[i-1].x||s[i].y!=s[i-1].y||s[i].z!=s[i-1].z)a[++n]=s[i];
    CDQsolve(1,n);
    for(int i=1;i<=n;i++)cnt[a[i].ans+a[i].t-1]+=a[i].t;
    for(int i=0;i<m;i++)cout<<cnt[i]<<"\n";
    return 0;
}

说白了，其本质就是——分治套上树状数组。

CDQ 分治优化 DP

这个东西不是最板的 CDQ 分治了，它明显是一个求最长上升子序列一样的东西，但是，显而易见的，这个规则很奇怪，所以不能直接用最简单的求最长上升子序列的方法。

这个时候咱们的 CDQ 分治就又出场啦——CDQ 分治是可以用来优化 DP 的哦！

其本质非常简单，就是在模板 CDQ 分治统计答案的时候，把它改造成一个 DP 的转移式就行了。

换句话说，就是把 s[i].ans+=ask(a[p2].z) 这句话修改为 s[p2].dp=max(s[p2].dp,ask(s[p2].d)+1)，就成功实现了 CDQ 优化 DP 的一个过程。

当然，这题不是最无聊的偏序问题，所以一开始要提炼一下乱七八糟的题面，将其弄成数学式的形式，然后整个题目就特别显然易懂了。

最开始还需要离散化一下。

注意细节。千万不要像我一样树状数组上界给了个 0 自己还没发现！

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5;
struct node{int a,b,c,d,dp;}s[N];
int ppp,m,n,r[3*N],ans;map<int,int> mp;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp1(node d1,node d2){return d1.a<d2.a;}
bool cmp2(node d1,node d2){return d1.d<d2.d;}
bool cmp3(node d1,node d2){return d1.b<d2.b;}
void clr(int x){while(x<=ppp)r[x]=0,x+=x&-x;return;}
void add(int x,int k){while(x<=ppp)r[x]=max(r[x],k),x+=x&-x;return;}
int ask(int x){int sum=0;while(x)sum=max(sum,r[x]),x-=x&-x;return sum;}
void CDQsolve(int l,int r){
    if(l==r)return;
    sort(s+l,s+r+1,cmp1);
    int mid=(l+r)>>1;CDQsolve(l,mid);
    sort(s+l,s+mid+1,cmp2),sort(s+mid+1,s+r+1,cmp3);
    int p1=l,p2=mid+1;
    for(int i=l;i<=r;i++)
        if(p2>r||(p1<=mid&&s[p1].d<=s[p2].b))add(s[p1].c,s[p1].dp),p1++;
        else s[p2].dp=max(s[p2].dp,ask(s[p2].d)+1),p2++;
    for(int i=l;i<=mid;i++)clr(s[i].c);
    CDQsolve(mid+1,r);return;
}
int main(){
    n=read();ppp=3*n;
    for(int i=1;i<=n;i++)
        s[i].a=read(),s[i].b=read(),s[i].c=read(),s[i].d=read();
    for(int i=1;i<=n;i++)
        mp[s[i].b]=1,mp[s[i].c]=1,mp[s[i].d]=1;
    int now=0;for(auto &it:mp)it.se=(++now);
    for(int i=1;i<=n;i++)
        s[i].b=mp[s[i].b],s[i].c=mp[s[i].c],s[i].d=mp[s[i].d];
    for(int i=1;i<=n;i++)s[i].dp=1;
    CDQsolve(1,n);
    for(int i=1;i<=n;i++)ans=max(ans,s[i].dp);
    cout<<ans<<"\n";
    return 0;
}

CDQ 分治求解四维偏序问题

正如我开头所提到的，CDQ 分治也可以用来求解四维偏序问题，但是需要用到 CDQ 分治套 CDQ 分治的写法。

这里就用一道例题简单说一下。同样的，也是一个 CDQ 分治优化 DP 哦。

大概的一个思想就是，首先外面有一层 CDQ 分治去处理掉四维偏序中的一个维度，然后再在里面塞一个 CDQ 分治去弄剩下的三维。

不过由于外层 CDQ 处理其中一维的时候已经标定了顺序，所以内层 CDQ 分治在塞进树状数组以及查询树状数组的时候需要判断一下，只有在指定的某一边的时候才能够进行统计，不然外面那一圈是乱的。

然后整个就结束了，注意细节。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 5e4+5;
struct node{int a,b,c,d,e,id,t;}p[N],h[N],s[N];
int m,n,ppp,ans,r[N],dp[N];map<int,int> mp;
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool operator != (const node &A , const node &B){
    return (A.a!=B.a||A.b!=B.b||A.c!=B.c||A.d!=B.d);
}
bool cmp1(node d1,node d2){
    if(d1.a!=d2.a)return d1.a<d2.a;
    if(d1.b!=d2.b)return d1.b<d2.b;
    return (d1.c<d2.c||(d1.c==d2.c&&d1.d<d2.d));
}
bool cmp2(node d1,node d2){
    if(d1.b!=d2.b)return d1.b<d2.b;
    return (d1.c<d2.c||(d1.c==d2.c&&d1.d<d2.d));
}
bool cmp3(node d1,node d2){
    return (d1.c<d2.c||(d1.c==d2.c&&d1.d<d2.d));
}
void clr(int x){while(x<=ppp)r[x]=0,x+=x&-x;return;}
void add(int x,int k){while(x<=ppp)r[x]=max(r[x],k),x+=x&-x;return;}
int ask(int x){int sum=0;while(x)sum=max(sum,r[x]),x-=x&-x;return sum;}
void CDQ2(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;CDQ2(l,mid);
    stable_sort(h+l,h+mid+1,cmp3);
    stable_sort(h+mid+1,h+r+1,cmp3);
    int p1=l,p2=mid+1;
    for(int i=l;i<=r;i++)
        if((p2>r)||(p1<=mid&&h[p1].c<=h[p2].c))
            {if(!h[p1].e)add(h[p1].d,dp[h[p1].id]);p1++;}
        else{if(h[p2].e)dp[h[p2].id]=max(dp[h[p2].id],ask(h[p2].d)+h[p2].t);p2++;}
    for(int i=l;i<=mid;i++)if(!h[i].e)clr(h[i].d);
    stable_sort(h+mid+1,h+r+1,cmp2);CDQ2(mid+1,r);return;
}
void CDQ1(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;CDQ1(l,mid);
    for(int i=l;i<=r;i++)h[i]=s[i],h[i].e=(i>mid);
    stable_sort(h+l,h+r+1,cmp2);
    CDQ2(l,r);CDQ1(mid+1,r);return;
}
int main(){
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d;
    for(int i=1;i<=m;i++)mp[p[i].d]=1;
    ppp=0;for(auto &it:mp)it.se=(++ppp);
    for(int i=1;i<=m;i++)p[i].d=mp[p[i].d];
    stable_sort(p+1,p+m+1,cmp1);
    for(int i=1;i<=m;s[n].t++,i++)
        if(p[i]!=p[i-1])s[++n]=p[i],s[n].id=n;
    for(int i=1;i<=n;i++)dp[i]=s[i].t;
    stable_sort(s+1,s+n+1,cmp1);CDQ1(1,n);
    for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
    cout<<ans<<"\n";
    return 0;
}

CDQ 分治练习题

这是一道 CDQ 分治的简单运用题。

可以发现这道题目只需求出数组一开始拥有的逆序对数量，之后依次计算减少的逆序对数量即可。

而一个数被删除的时间在计算逆序对时非常重要，因此逆序对就多了一个名为“删除时间”的变量，其也会影响到逆序对的计算。

然后它就成了一个比较显然的 CDQ 分治了，按照通常的处理方式计算即可，注意在分治函数内部需要执行两次 while 以精准统计，并且还需要清空树状数组。

细节有点繁琐。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 2e5+5;
struct node{LL x,del,sum;}a[N];
LL n,m,Pid[N],Res,e[N];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp1(node d1,node d2){return d1.x<d2.x;}
bool cmp2(node d1,node d2){return d1.del<d2.del;}
void add(LL x,LL k){while(x<=n+1)e[x]+=k,x+=x&-x;return;}
LL ask(LL x){LL sum=0;while(x)sum+=e[x],x-=x&-x;return sum;}
void CDQsolve(int l,int r){
    if(l==r)return;int mid=(l+r)/2;
    CDQsolve(l,mid),CDQsolve(mid+1,r);
    int p1=l,p2=mid+1;
    while(p1<=mid){
        while(a[p1].x>a[p2].x&&p2<=r)add(a[p2].del,1),p2++;
        a[p1].sum+=ask(m+1)-ask(a[p1].del),p1++;
    }
    p1=l,p2=mid+1;while(p1<=mid)
        {while(a[p1].x>a[p2].x&&p2<=r)add(a[p2].del,-1),p2++;p1++;}
    p1=mid,p2=r;
    while(p2>mid){
        while(a[p2].x<a[p1].x&&p1>=l)add(a[p1].del,1),p1--;
        a[p2].sum+=ask(m+1)-ask(a[p2].del),p2--;
    }
    p1=mid,p2=r;while(p2>mid)
        {while(a[p2].x<a[p1].x&&p1>=l)add(a[p1].del,-1),p1--;p2--;}
    sort(a+l,a+r+1,cmp1);return;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i].x=read(),Pid[a[i].x]=i;
    for(int i=1;i<=n;i++)a[i].del=m+1;
    for(int i=1;i<=m;i++){int x=read();a[Pid[x]].del=i;}
    for(int i=1;i<=n;i++)Res+=ask(n+1)-ask(a[i].x),add(a[i].x,1);
    for(int i=0;i<=n+1;i++)e[i]=0;CDQsolve(1,n);
    sort(a+1,a+n+1,cmp2);
    for(int i=1;i<=m;i++){cout<<Res<<"\n";Res-=a[i].sum;}
    return 0;
}

简单总结 CDQ 分治

CDQ 分治，是一个用来处理偏序问题的算法，其本质就是将归并排序的思想（即分治）与树状数组相结合，成功在 O(n \log ^2 n) 的时间复杂度下完美解决三维偏序问题。其也可以通过自己套自己的方式解决四维偏序问题，用处很广。当然，它经常用于优化 DP，最长上升子序列，或者类似于题目重载了一个比较符的形式的 DP 都可能会运用到它。

码这么多字也不容易，还麻烦你留个赞支持一下，真是太感谢啦！