引言在算法竞赛中我们经常遇到这样的问题给定若干个点每个点有多个属性维度统计满足某些偏序关系的点对数量。这就是多维偏序问题。最朴素的做法是枚举所有点对复杂度 O(n2)当 n^2 达到 1051e5 时显然不可行。解决偏序问题的常见思路是降维通过排序去掉一维用数据结构去掉一维剩下的维度……怎么办CDQ分治正是为了解决这个问题而生的。CDQ分治由2008年IOI金牌得主陈丹琦在高中时整理并总结的一种分治思想。它的核心思想是分治 归并 贡献计算——将序列递归地分成左右两半每个子问题只处理跨左右区间的贡献。通过这种方式每使用一次CDQ分治就能降掉一维将高维偏序问题转化为低维问题。如果说暴力枚举是“逐一比较一个不漏”那么CDQ分治就是“分而治之只算跨界的账”——它把问题切成两半分别处理再单独计算两半之间的贡献避免了重复计算。前置知识在学习CDQ分治之前你需要掌握以下基础分治思想将大问题分解为若干子问题分别解决后合并答案。归并排序就是分治的典型例子。偏序关系一种具有自反性、反对称性、传递性的二元关系。例如三维偏序中点 AA 优于点 BB 当且仅当 AA 的三个属性都分别大于等于 BB 的三个属性。树状数组支持单点修改和前缀查询的数据结构O(log⁡n) 操作。离线算法CDQ分治要求所有操作预先知道不能在线处理。第一章从一维到三维——偏序问题的降维之路1.1 一维偏序排序一维偏序问题最简单给定 nn 个数统计每个数前面有多少个数小于等于它。直接排序即可复杂度 O(nlog⁡n)。1.2 二维偏序排序 树状数组二维偏序问题给定 nn 个二元组 (x,y(x,y)对每个点统计满足 xj≤xi​ 且 yj≤yi 的点的个数。做法先按 x 从小到大排序然后依次遍历每个点在树状数组中查询 y 的前缀和作为答案再将当前点的 y 加入树状数组。这就是“排序去掉一维数据结构去掉一维”的思路。1.3 三维偏序排序 CDQ分治 树状数组三维偏序问题即陌上花开问题给定 nn 个三元组 (a,b,c)对每个点统计满足 aj≤ai​、bj≤bi、cj≤ci的点的个数。三维偏序无法简单地用“排序 树状数组”解决因为还有第三维。CDQ分治在这里登场了第一维排序按 a 排序去掉 a 这一维。第二维CDQ分治在分治过程中用归并的方式处理 b 维。第三维树状数组在CDQ分治的内部用树状数组维护 c 维。每使用一次CDQ分治就降掉一维。三维偏序用一层CDQ四维偏序可以用两层CDQ嵌套。第二章CDQ分治的核心思想2.1 分治框架CDQ分治处理点对贡献问题的基本框架如下solve(l, r): 1. 如果 l r返回 2. mid (l r) / 2 3. solve(l, mid) // 递归处理左半部分 4. solve(mid 1, r) // 递归处理右半部分 5. 计算左半部分对右半部分的贡献跨区间贡献关键洞察在solve(l, r)中点对 (i,j)(i,j) 被分为三类第一类i 和 j 都在左半部分 → 在solve(l, mid)中处理第二类i 和 j 都在右半部分 → 在solve(mid1, r)中处理第三类i 在左半部分j 在右半部分 →在当前层处理CDQ分治只处理第三类贡献前两类交给递归。为什么这样做是对的因为每个点对恰好会在某一层被处理一次当它们第一次被分到不同的子区间时就是它们被计算贡献的时候。2.2 为什么能降维在计算跨区间贡献时左右两个子区间各自内部的顺序变得不再重要。因为我们只关心左区间的点对右区间点的贡献而左区间的所有点在第一维上都小于等于右区间的所有点这是最初排序保证的。于是三维偏序变成了二维问题只需要在左右区间之间满足 bb 和 cc 的限制即可。2.3 CDQ分治的适用场景CDQ分治可以解决三类问题类型说明点对/偏序问题统计满足某种偏序关系的点对数量动态问题转静态将带修改和查询的动态问题按时间分治转化为静态问题优化1D/1D DP优化形如 dp[i]max⁡ji(dp[j]w(j,i))dp[i]maxji​(dp[j]w(j,i)) 的DP转移第三章三维偏序陌上花开详解3.1 问题描述有 nn 朵花每朵花有三个属性花形 (a)(a)、颜色 (b)(b)、气味 (c)(c)用三个整数表示。定义一朵花 AA 比另一朵花 BB美丽当且仅当 aA≥aBaA​≥aB​、bA≥bBbA​≥bB​、cA≥cBcA​≥cB​。显然两朵花可能有相同的属性。现要对每朵花评级一朵花的级别是它拥有的美丽能超过的花的数量。求每个级别各有多少朵花。3.2 算法流程第一步去重如果有多朵花属性完全相同它们之间相互都有贡献。但在CDQ分治中只有左边的能贡献给右边的。因此需要先去重给每个三元组记录一个权值cnt表示出现次数。第二步按第一维排序将所有元素按 aa 为第一关键字、bb 为第二关键字、cc 为第三关键字排序。这样保证了序列中后面的元素的 aa 一定大于等于前面的元素。第三步CDQ分治void cdq(int l, int r) { if (l r) return; int mid (l r) 1; cdq(l, mid); cdq(mid 1, r); // 处理跨区间贡献左区间 [l, mid] 对右区间 [mid1, r] 的贡献 // 将左右区间分别按 b 排序 sort(a l, a mid 1, cmp_b); sort(a mid 1, a r 1, cmp_b); int i l; for (int j mid 1; j r; j) { while (i mid a[i].b a[j].b) { add(a[i].c, a[i].cnt); // 将左区间中 b 满足条件的点加入树状数组 i; } a[j].ans query(a[j].c); // 查询 c 小于等于 a[j].c 的点的总数 } // 清空树状数组 for (int k l; k i; k) { add(a[k].c, -a[k].cnt); } }第四步统计答案每个点的最终答案 自身ans来自其他点的贡献cnt - 1相同元素内部的贡献。3.3 为什么需要去重CDQ分治中对于完全相同的两个元素排序后它们会有一个先后顺序。假设元素 xx 排在 yy 前面那么 xx 能贡献给 yy但 yy 不能贡献给 xx因为 yy 在右区间而 xx 在左区间时才能计算贡献。去重后相同元素合并为一个节点用cnt表示出现次数。在树状数组中插入的是cnt而不是 1最后答案加上cnt-1即可。3.4 复杂度分析排序O(nlog⁡n)CDQ分治每层排序 O(nlog⁡n)共 log⁡n 层总复杂度 O(nlog^⁡2n)如果用归并排序代替sort可以优化到 O(nlog⁡n)第四章CDQ分治优化DP4.1 核心思想DP 是指形如 dp[i]max⁡ji(dp[j]w(j,i)) 的转移方程。这类DP有两个特点jiji 是天然的偏序关系DP本身是离线的——计算 dp[i] 时所有 ji 的 dp[j] 都已经算好了CDQ分治优化DP的核心是中序遍历先处理左区间内部的DP再用左区间去更新右区间最后处理右区间内部的DP。这样可以保证计算 dp[i]dp[i] 时所有 jiji 的贡献都已经被考虑过了。4.2 典型例题P4093 [HEOI2016/TJOI2016] 序列题目描述给定一个序列每个位置的值可能发生变化求最长的子序列使得存在一种变化方式使这个子序列不降。解法记 mx[i] 为位置 ii 能变到的最大值mn[i] 为位置 i 能变到的最小值。转移条件为 ij、mx[i]≤a[j]、a[i]≤mn[j]。这是一个三维偏序条件下的DP用CDQ分治优化即可。第五章动态问题转静态——动态逆序对5.1 问题转化P3157 [CQOI2011] 动态逆序对给定一个 1∼n 的排列按顺序删除 m 个元素每次删除前输出当前序列的逆序对数。核心转化把“删除”倒过来看成“插入”。每个元素有一个出现时间t从未被删除的元素 t∞被删除的元素 t 等于它被删除的时刻。于是问题变成了三维偏序对于每个逆序对 (i,j)ij 且 aiaj它对答案有贡献当且仅当 titj​即 i 比 j 更晚被删除或者说 j 先消失。三个维度分别是位置、数值、删除时间。5.2 CDQ分治求解按位置排序后CDQ分治用树状数组维护数值维统计满足 titj且 aiaj的点对数量。由于逆序对有两种情况ij且 aiaj以及 ij 且 aiaj​ 对反向的贡献需要分别统计。最后对每个时间点做前缀和得到每个删除时刻的逆序对数。第六章例题与解析例题1三维偏序陌上花开—— 洛谷 P3810题目描述有 nn 个元素每个元素有三个属性 a,b,c。定义 f(i) 表示有多少个 j 满足 aj≤ai​、bj≤bi、cj≤ci 且 j≠i。求每个 f(i) 的值的出现次数。解题思路直接套用CDQ分治模板。注意去重和树状数组清空。核心代码cppstruct Node { int a, b, c, cnt, ans; } q[N], tmp[N]; bool cmp_a(Node x, Node y) { if (x.a ! y.a) return x.a y.a; if (x.b ! y.b) return x.b y.b; return x.c y.c; } bool cmp_b(Node x, Node y) { if (x.b ! y.b) return x.b y.b; return x.c y.c; } void cdq(int l, int r) { if (l r) return; int mid (l r) 1; cdq(l, mid); cdq(mid 1, r); sort(q l, q mid 1, cmp_b); sort(q mid 1, q r 1, cmp_b); int i l; for (int j mid 1; j r; j) { while (i mid q[i].b q[j].b) { add(q[i].c, q[i].cnt); i; } q[j].ans query(q[j].c); } for (int k l; k i; k) { add(q[k].c, -q[k].cnt); } }复杂度O(nlog⁡^2n)。例题2动态逆序对 —— 洛谷 P3157题目描述给定一个 1∼n 的排列按顺序删除 m 个元素每次删除前输出当前序列的逆序对数。解题思路将删除转化为插入给每个元素加上时间维 t转化为三维偏序问题。核心思想每个元素有三维(时间,位置,数值)一个逆序对 (i,j) 对答案有贡献当且仅当 titj​、posiposj、valivalj用CDQ分治统计所有满足条件的点对复杂度O(nlog^2n)。总结CDQ分治是一种思想而非具体算法它的核心是“分治 归并 贡献计算”。通过将序列递归分成两半只计算跨区间的贡献CDQ分治能够解决多维偏序问题每使用一次CDQ分治降掉一维将动态问题转为静态按时间分治将修改和查询转化为偏序关系优化1D/1D DP利用分治顺序保证DP计算的正确性学习CDQ分治的三个关键点理解“跨区间贡献”每个点对只在第一次被分开时计算一次掌握降维的顺序排序 → CDQ → 数据结构逐层剥离维度注意去重和清空重复元素需要合并树状数组需要精确清空