#创作计划 浅谈CDQ分治
2026-03-20 14:13:30
发布于：重庆
CDQ分治
闲话
依旧是一年前写的。
一些定义
分治中心：就是常说的 ，划分两个区间的分割点，普通分治取 。
引入
分治这个东西的本质就是做信息划分，通过把信息划分成两个部分然后对一个部分的信息做整体合并，另一个信息做整体查询，做到优化时间复杂度的目的。
比如说这样一个经典的问题：求一个序列的逆序对数。形式化来说就是求出 且 的二元组 个数，这里可以使用数据结构来做，但是先抛开它不谈。
你可能听说过：这不是归并排序的时候顺便求一下就可以了吗？当然是对的，但是它的本质是什么。
归并排序的分治过程是这样的：
-
先递归处理区间 和 ，将这两个区间里的数排序。
-
依次比较两个区间的每个数，分别维护一个头指针，记作 ，比较这两个数的大小，将较小的一个放到临时数组里做归并。
-
将临时数组的信息复制到原数组。
计算逆序是在第二步，我们考虑 天然的性质：这里面的所有数的原编号都大于 ，这是毋庸置疑的。同时，考虑计算贡献，由于两个数组此时是单调的，所以此时 中比 位置上大的数区间为 ，贡献就是 ，当然需要满足 。
时间复杂度是 的，递归 层并且一层均摊 。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,a[N],b[N],ans;//原数组，临时数组
void solve(int l,int r){
if(l==r)return;int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r);//递归处理[l,mid]和[mid+1,r]让它们相对于有序
int i = l,j = mid+1, k = l;
while(i<=mid&&j<=r){
if(a[i]<=a[j])b[k++]=a[i++];//这里有个细节，a[i]<=a[j]
else ans+=mid-i+1,b[k++]=a[j++];//此时满足a[i]>a[j]，也就是说[i,mid]中的所有数都大于a[j]，逆序对贡献mid-i+1
}
while(i<=mid)b[k++]=a[i++];
while(j<=r)b[k++]=a[j++];//将剩下的数一次放入
for(int i = l;i <= r;i++)a[i]=b[i];//还原
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i];
solve(1,n);
cout << ans;
return 0;
}
一般偏序问题
比较形式化的问题。
偏序问题的定义
简单来说就是有 个元素，每个元素有若干组信息（维度），然后偏序就是两个元素的每个维度上的信息满足一些大小关系。
比如说刚刚的逆序对问题可以把每个数看做二元组 ，满足贡献就是 $a_i > a_j $ 并且 ，这就是一个偏序问题。
CDQ基本思路
刚刚解决逆序对问题我们是按照这个思路走的：
- 将区间内的点对按照位置划分成三部分:
-
且 ，左部点在 右部点在 。
-
，都在 。
-
，都在 。
- 分治处理第一类区间，递归去做另外的子问题。
这是分治的基本思路，当然可能递归顺序有所不同，但是本质上都是处理第一部分的点对。
同时，对于偏序问题而言我们有一个设计思路：排序维护单调性。
以三维偏序为例，每个元素有 三维，一个点对合法的条件是：同时满足 。
这个思路很重要，设计算法就是这样设计，敲黑板！
和刚刚的归并排序一样，我们强制让一维有序，这一点我们对原数组排个序。分治的时候就时刻保证 中的所有数至少在一维上相对 的数是有序的，这里我们按 从小到大排序。
既然如此，我们也就不在意它们的顺序，不妨让 和 在第二维 上分别有序，这样维护出来单调性就可以通过双指针来动态维护 某一个位置 的偏序信息，本质是一个集合。
第三维此时，排序有点排不动了......但是我们可以把这个统计问题看做是算一个前缀信息，换句话说：序列上单点加区间求和。树状数组或者线段树随便上一个就可以了。
回顾一下 CDQ 分治的设计思路：
-
整体排序，保证第一维单调性。
-
做归并，合并信息前保证 和 在第二维相对有序。
-
通过数据结构维护第三维信息。
恭喜你学会了 CDQ 分治，这是模版题。
变种
一些题的套路，考来考去其实都是这样的。
时间轴上的问题
一些维护操作的问题一般都会有操作时效性，就是说一个操作只对它后面的询问或者操作有影响，这是天然的一维排序。
考虑这个问题：在一个二维平面直角坐标系上支持单点加一个数，统计某个矩形内所有数的和。
首先矩形我们有一个常规的做法：二维差分。对于一组询问 我们拆分成四个询问 。也就是矩形差分，画图的话大概是这样的：
所以我们只需要考虑统计三元组 ，也就是满足 的信息。
时间是天然有序的，直接分治就可以只需要考虑坐标维，使用 BIT（树状数组）就可以了。
代码非常好写。
优化转移
这个实际上基本才是 CDQ 的基本用途，用于优化一些条件类似偏序的动态规划转移。
来看这样一个问题:P4093 [HEOI2016/TJOI2016] 序列
序列变化只是干扰因素。我们考虑动态规划，记一个位置的可能最大值为 ，可能最小值为 ， 表示以 结尾的答案。满足以下条件时可进行转移：
，，，此时 可转移到 。由于序列每次最多产生一种变化，所以只需考虑两种极端情况。
此时，考虑 CDQ 分治的时候，我们的递归顺序不太一样，是先递归 然后根据 的信息对 做批量更新，然后考虑继续递归 。
原理很简单，分析下转移路径的顺序就可以了。本质上，就是在分治树上做中序遍历，分治的顺序同时也很重要。
课后例题
这里空空如也
有帮助，赞一个