浅谈 CDQ 分治

xiao7_Mr_10_ · 2025-03-20 16:04:51 · 个人记录

引入

CDQ 分治，作为算法竞赛里极为常见的分治思想，常被用于统计点对间的贡献，以此优化复杂度。2008 年由陈丹琦首次提出，她还撰写了一篇论文，其中阐述了利用 CDQ 分治处理偏序问题以及优化动态规划（dp）的方法。感兴趣的同学可查看论文：从《Cash》谈一类分治算法的应用。

定义

• 偏序问题：通常是需处理点对关系进而统计答案的问题。例如逆序对问题，便是典型的二维偏序问题，涉及编号和数组值这两维。二维矩阵内的数据查询本质上也是偏序问题。在 OI 领域，偏序问题颇为常见，常出现在数据结构或数学类题目中。
• 分治中心：分治时选取的分割点，一般简单地取区间中点 mid。但也有特殊情况，像后续要讲的笛卡尔树分治，是以找区间最值的位置作为分割点，所以它也叫极值分治，其本质是二叉树，可用单调栈以 O(n) 时间复杂度建树，后续文章将详细讲解该算法。

经典选讲

静态问题

（ps：此部分讲解十分详细，若已掌握 CDQ 分治基本原理，可跳过。）

以经典题目 P3810 【模板】三维偏序（陌上花开）展开探讨，题目大意如下：

给定 n 个三元组 (a_i,b_i,c_i)，对于每个 i \in [1,n]，需找出满足 a_j \leq a_i，b_j \leq b_i，c_j \leq c_i 且 j \neq i 的 j 的数量。

乍看之下，题目存在三个条件，还需对每个 i 求解，似乎难以优化。

暴力解法很直接，先简化问题：若仅存在 a_j 的限制该如何处理？显然，我们可存储一个结构体，记录每个数的原始位置和值，然后按值从小到大排序。假设第 i 个二元组为 (id_i,val_i)，那么 ans_{id_i} = i - 1。这就是最简单的偏序问题，时间复杂度为 O(n \log n)，瓶颈在于排序。

将问题拓展到二维偏序，其实也不难解决。沿用上述思路，先按 a 从小到大排序，接着考虑如何消除 b 维度的限制。

采用最朴素的分治算法，设当前处理区间 [l,r] 的递归函数为 solve(l,r)，分治中心为 mid=\lfloor \frac{l + r}{2} \rfloor。

由于已按 a 排序，区间 [l,mid] 中 a 的值必然不超过 [mid + 1,r]。此时便消除了第一维偏序的影响。假设此时两个区间内 b 单调，就可用双指针统计答案，这较容易实现。通过归并排序的方法可维护 b 的单调性，时间复杂度仍为 O(n \log n)。

至此，对于三维偏序问题，我们可尝试再消除一维影响来统计答案。

若要消除 c_i 的影响，排序的方法不太可行，因为无法消除第三维的影响。不过解决办法也简单，在处理二维偏序时，我们能将合法贡献计入答案数组，这里不妨借助数据结构来维护第三维偏序。

算法流程如下：

1. 先递归处理 solve(l,mid) 和 solve(mid + 1,r) 的答案，若递归到底则直接退出。
2. 枚举右区间 [mid + 1,r] 的数 i，表示当前处理 i 的答案。
3. 左区间 [l,mid] 的指针 j 同时移动，维护所有 b_j \leq b_i 的答案，并将对应的 c_j 加入数据结构。
4. 查询满足 c_i \geq c_j 的数量，只需用支持单点加、区间查的数据结构即可，这里推荐常数小且易实现的树状数组。

简单证明一下复杂度，处理一个区间内的答案复杂度实际为 O(len \log n)，其中 len 为区间长度，\log n 为数据结构自带的复杂度。

所以有 T(n)=T(\frac{n}{2}) \times 2 + O(len \log n)，时间复杂度为 O(n \log n^2)，实际上多数 CDQ 分治题目都是这个复杂度。

但可能有人疑惑，为何要先递归处理两个子区间的答案？这涉及分治算法优化的本质。实际上，几乎所有分治算法都可归结为以下模型：

1. 处理两个分治区间内的点对信息。
2. 处理横跨分治中心的点对信息。

这样做是因为合并信息的复杂度小于暴力枚举，只要能限制分治区间的递归层数以及合并总复杂度，算法基本可行。

CDQ 分治先处理情况 1，再处理情况 2，这无疑是正确的。当合并答案不影响后续答案查询时，也可调整顺序。

以下是 CDQ 分治的主体代码（我初一时候写的……）：

void work(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
        work(l,mid);
    work(mid+1,r);
    sort(b+l,b+1+mid,cmp1);
    sort(b+1+mid,b+1+r,cmp1);
    int i = l,j = mid+1;//这就是双指针
    for(;j<=r;j++){
        while(i<=mid&&b[i].y<=b[j].y){
            insert(b[i].z,b[i].cnt);//这个是树状数组
            i++;
        }
        b[j].val+=query(b[j].z);//更新答案
    } 
    for(int k = l;k < i;k++)insert(b[k].z,-b[k].cnt);//记得撤销影响
}

带修问题

对刚刚的内容有了一个深入理解后，这部分难度并不大。很多 CDQ 难题本质上是数据结构问题，常以 CDQ 分治为辅或依赖巧妙结论。

比如有些题目需要支持修改操作，本质是分治时按时间轴对操作分类。可参考这道题，它属于待修问题综合运用中较简单的一类。

题目要求求出某点 (x_i,y_i) 与询问点曼哈顿距离 的最小值。根据定义，可将问题简化：

假设以点 (x,y) 为坐标轴原点，依次处理四个象限的最小值，去掉绝对值后再统计答案。

实际上，这是个三维偏序问题，三维分别为加入时间（时间戳）、横坐标、纵坐标。

设三元组 (t_i,x_i,y_i)，对于第一象限，计入答案贡献的点对需满足：t_j \leq t_i，x_j\leq x_i，y_j \geq y_i。

实际上，这里 t 不可能取等，不过不影响处理，简单处理即可。结合上述算法，维护一个支持单点加、区间查最小值的数据结构，这里仍采用树状数组，只需将加法操作改为取 \min 操作。

处理其他象限方法类似，可通过对坐标做轴对称变换来转化坐标，这是简单的求对称点问题，稍作计算即可。

这道题还有些卡常优化细节。值得注意的是，上一道例题本质上也是插入 n 个点并处理 n 个询问，只是条件不同，这启示我们可将初始序列视为一种操作，插入操作序列最前端。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,maxn=1e6+3;
struct Point{
    int x,y,id,op;
    bool operator < (const Point &tlh)const{//不要在意......
        return x<=tlh.x;
    }
}a[N],lq[N],tl[N],tld[N];
int n,m,x,y,maxn1,maxn2,tlh,ans[N],c[N];
void add(int x,int y){for(;x<=maxn;x+=x&(-x))c[x]=max(c[x],y);}
int query(int x){int ans=0;for(;x;x-=x&(-x))ans=max(ans,c[x]);return ans;}
void clear(int x){for(;x<=maxn;x+=x&(-x))c[x]=0;}
void cdq(int l,int r){
    if(l==r)return;int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int j = l;
    for(int i = mid+1;i <= r;i++){
        if(a[i].op==2){
            for(;j<=mid&&a[j].x<=a[i].x;j++)if(a[j].op==1)add(a[j].y,a[j].x+a[j].y);
            if(query(a[i].y))ans[a[i].id]=min(ans[a[i].id],a[i].x+a[i].y-query(a[i].y));
        }
    }for(int i = l;i < j;i++)if(a[i].op==1)clear(a[i].y);
        merge(a + l, a + mid + 1, a + mid + 1, a + r + 1, tld + l);
    for (int i = l; i <= r; ++i) a[i] = tld[i];
}
void init(){
    int val1=0,val2=0;m=0;
    for(int i = 1;i <= n;i++)if(a[i].op==2)val1=max(val1,a[i].x),val2=max(val2,a[i].y);
    for(int i = 1;i <= n;i++)if(a[i].x<=val1&&a[i].y<=val2)tl[++m]=a[i];
    for(int i = 1;i <= m;i++)a[i]=tl[i];    
}
Point make(Point tlh,int tag1,int tag2){
    if(tag1)tlh.x=maxn1-tlh.x;
    if(tag2)tlh.y=maxn2-tlh.y;return tlh;
}int q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    cin >> n >> q;
    for(int i = 1;i <= n;i++){
        cin >> x >> y;x++,y++;
        a[i]=(Point){x,y,i,1};maxn1=max(maxn1,x),maxn2=max(maxn2,y);
    }
    for(int i = 1;i <= q;i++){n++;
        cin >> a[n].op >> a[n].x >> a[n].y;a[n].x++,a[n].y++;maxn1=max(maxn1,a[n].x),maxn2=max(maxn2,a[n].y);
        if(a[n].op==2)a[n].id=++tlh;
    }for(int i= 1;i <= n;i++)lq[i]=a[i];memset(ans,0x3f,sizeof(ans));maxn1++,maxn2++;
    if(tlh){
        for(int i = 0;i < 2;i++){
            for(int j = 0;j < 2;j++){
                for(int k = 1;k <= n;k++)a[k]=make(lq[k],i,j);
                init();cdq(1,m);
            }
        }
    }
    for(int i = 1;i <= tlh;i++)cout << ans[i] <<"\n";
    return 0;
}

CDQ 优化 dp

以本题 为例，大家可先自行读题思考。

序列变化只是干扰因素。我们考虑动态规划，记一个位置的可能最大值为 mx_i，可能最小值为 mn_i，f_i 表示以 i 结尾的答案。满足以下条件时可进行转移：