第 118 章 CDQ 分治¶
本章配套 1 道例题，见 §例题。 前置：分治的三步框架、排序、树状数组、偏序集与Dilworth定理
CDQ 分治用分治代替「一个维度的数据结构」：三维偏序里，第一维排序、 第二维分治、第三维树状数组。它的前身是归并分治——「让前半影响后半」的最简形态， 本章从逆序对讲起，一路推到三维偏序与「动态问题静态化」。
在 Python 里学它的理由不是速度，是「离线」这条路： 线段树跑不动的时候，问一句「能不能不在线」，往往能把 \(O(q\log n)\) 的在线代价摊成 \(O(q\log q)\) 的小操作。
分治的三个层次¶
| 层次 | 分的是什么 | 合并时算什么 | 典型问题 |
|---|---|---|---|
| 归并分治 | 下标（序列对半砍） | 「左半 × 右半」的跨中线贡献 | 逆序对、最近点对、最大子段和 |
| 整体二分 | 值域 + 询问集合 | 用一个数据结构判定每个询问该去左还是右 | 静态/动态区间第 \(k\) 小、二分答案的批处理 |
| CDQ 分治 | 时间/下标 | 「前半的修改」对「后半的询问」的影响 | 三维偏序、带修改的偏序问题 |
三者的共同点：都是「把「所有对」拆成 \(O(\log n)\) 层，每层只处理跨中线的那些对」。 差别只在「分的是什么维度」。
同一层次里分「值域 + 询问集合」的那一支是 整体二分； 通用框架与主定理在 分治的三步框架。
1 归并分治：从逆序对说起¶
归并排序的合并步是「两个有序段合成一个有序段」，\(O(n)\)。 它的副产品是逆序对：
归并时若从右半取走一个元素
right[j]， 说明左半剩下的len(left) - i个元素全都比它大且都在它前面， 一次性贡献这么多逆序对。
完整实现见 排序 · 归并的真正用途，这里只放核心一行：
# [片段]
while i < nl and j < len(right): # 两半各有一个游标，谁小谁先出队
if left[i] <= right[j]: # <= 保证稳定
res.append(left[i]); i += 1
else:
res.append(right[j]); j += 1
cnt += nl - i # ★ 左半剩余的元素都与它构成逆序对
# left[i:] 里每个都 > right[j] 且下标更靠前
归并分治的通用模式¶
任何「统计满足某条件的下标对 \((i,j)\)，\(i<j\)」的问题都可以试这个模式：
solve(l, r):
if l == r: return
mid = (l + r) // 2
solve(l, mid); solve(mid+1, r)
统计「i 在左半、j 在右半」且满足条件的对数 ← 唯一需要动脑的地方
把两半按某个键归并成有序（为上层的统计做准备）
| 问题 | 跨中线的统计 | 复杂度 |
|---|---|---|
| 逆序对 | 归并时数「左半剩余个数」 | \(O(n\log n)\) |
| 满足 \(a_i > 2a_j\) 的对数 | 双指针在两个有序段上扫 | \(O(n\log n)\) |
| 最近点对 | 按 \(x\) 分，只检查中线两侧 \(\pm d\) 条带内按 \(y\) 排序的相邻 7 个点 | \(O(n\log n)\) |
| 最大子段和 | 跨中线的最大和 = 左半后缀最大 + 右半前缀最大 | \(O(n\log n)\)（不如 DP 的 \(O(n)\)） |
| 区间 \([l,r]\) 内值在 \([x,y]\) 的个数（离线） | 归并 + bisect |
\(O(n\log^2 n)\) |
归并分治 vs 树状数组：这两者能解决的问题高度重叠。 逆序对既能归并分治也能「离散化 + 树状数组倒序扫」， 因为两者本质上都是「把二维偏序拆成一维扫描 + 一维数据结构」。 实测两者在 \(n=10^5\) 时都是 0.16 s，打成平手（见 §3 的实测表）。
选择依据： - 值域好离散化、只统计「个数」→ 树状数组（代码短、无递归）； - 需要在合并时做复杂的双指针/
bisect逻辑 → 归并分治； - 需要「按时间分治」（带修改）→ 只能 CDQ。
2 CDQ 分治¶
从「二维偏序」到「三维偏序」¶
偏序集与 Dilworth 定理 建立了偏序的语言。回顾一下维数的递进：
| 维数 | 问题 | 做法 |
|---|---|---|
| 一维 | 排序 | sort |
| 二维 | 逆序对 / LIS / 二维数点 | 一维排序 + 一维数据结构（树状数组） |
| 三维 | 三维偏序：对每个 \(i\) 求 \(\lvert\{j: a_j\le a_i, b_j\le b_i, c_j\le c_i\}\rvert\) | 一维排序 + 一维 CDQ + 一维数据结构 |
| 四维 | — | CDQ 套 CDQ，或 K-D 树 / bitset 暴力 |
三维偏序的标准三段式：
CDQ 的本质：让「前半」影响「后半」¶
cdq(l, r):
if l == r: return
mid = (l + r) // 2
cdq(l, mid) ← 先递归，保证左半内部已算完
cdq(mid+1, r)
统计「左半的元素」对「右半的元素」的贡献 ← 唯一动脑的地方
按第二维把两半归并（为上层准备）
为什么这样能不重不漏：任意一对 \((j, i)\) 且 \(j < i\)（第一维已有序）， 在递归树上恰好有一层让 \(j\) 落在左半、\(i\) 落在右半。 所以每一对被统计恰好一次。
这是 CDQ 与归并分治的唯一区别： - 归并分治统计的是「对称的贡献」（逆序对：左半元素与右半元素互相构成逆序对）； - CDQ 统计的是「单向的贡献」（左半的「修改」影响右半的「询问」，反之不影响）。
所以 CDQ 又被叫作「按时间分治」——第一维通常就是时间/操作序号。
模板：三维偏序¶
# [片段]
def cdq3d(pts, K):
"""三维偏序（洛谷 P3810 陌上花开）。
pts —— [(a, b, c)] 列表；K —— c 的值域上界
返回 cnt，cnt[d] = 「f 值恰为 d」的元素个数，
其中 f(i) = |{j != i : a_j<=a_i, b_j<=b_i, c_j<=c_i}|。
三段式：a 排序 -> b 用 CDQ -> c 用树状数组。
★ 完全相同的三元组必须**合并去重**，否则它们之间会互相少算。
复杂度 O(n log^2 n)。
"""
n = len(pts)
pts = sorted(pts) # 第一维 a：排序消掉
uniq = [] # 去重，w 记重数
w = []
for p in pts:
if uniq and uniq[-1] == p: # 排好序后相同三元组必然相邻，一次扫描即可去重
w[-1] += 1
else:
uniq.append(p)
w.append(1)
m = len(uniq)
f = [0] * m # f[i]：严格来自「别的三元组」的支配计数
bit = [0] * (K + 1) # 树状数组按 c 的值建，所以开到值域上界 K
def add(i, v): # 第三维 c：树状数组
while i <= K:
bit[i] += v
i += i & -i
def pre(i):
s = 0
while i > 0: # 前缀和 = 已入库元素里 c 值 <= i 的个数
s += bit[i]
i -= i & -i
return s
def solve(lo, hi, ids):
"""ids 是 [lo, hi] 内元素的 id 列表，按 a 序（即 id 升序）传入，
返回按 b 排好序的 id 列表。"""
if lo == hi:
return [ids[0]] # 单个元素天然有序，且自己不会支配自己
mid = (lo + hi) // 2
L = solve(lo, mid, ids[:mid - lo + 1]) # 递归后 L 已按 b 有序
R = solve(mid + 1, hi, ids[mid - lo + 1:]) # R 同理；两半内部的贡献已算完
# ---- 归并：b 小的先处理；左半元素「入库」，右半元素「查询」 ----
res = []
touched = [] # 记下本层入过库的元素，末尾要撤
i = j = 0
while i < len(L) and j < len(R):
if uniq[L[i]][1] <= uniq[R[j]][1]: # <= ：b 相等也满足偏序，左边要先入库
add(uniq[L[i]][2], w[L[i]]) # 左半 -> 入库
touched.append(L[i])
res.append(L[i]); i += 1
else:
f[R[j]] += pre(uniq[R[j]][2]) # 右半 -> 查库
res.append(R[j]); j += 1 # 库里此刻恰是 a 更小、b 不更大的那些
while i < len(L):
res.append(L[i]); i += 1 # 右半查完了，左半剩的只需并进结果
while j < len(R):
f[R[j]] += pre(uniq[R[j]][2]) # ★ 左半已全部入库，右半剩余也要查
res.append(R[j]); j += 1
for x in touched: # ★ 撤销，别污染兄弟分支
add(uniq[x][2], -w[x])
return res # 返回按 b 有序的合并结果，供上一层用
solve(0, m - 1, list(range(m)))
cnt = [0] * n
for i in range(m):
cnt[f[i] + w[i] - 1] += w[i] # 同值元素互相计入，故 +w-1
return cnt
自测（与 \(O(n^2)\) 暴力对拍 300 组随机小数据，全部一致）。
三个坑： 1. 完全相同的三元组必须去重合并。若 \((1,1,1)\) 出现 3 次， CDQ 只会让先出现的贡献给后出现的，导致答案偏小。 去重后用
w（重数）参与计算，最后f[i] + w[i] - 1补回来； 2. 归并的比较必须是<=而不是<。\(b\) 相等时也算「满足偏序」， 所以左半的相等元素要先入库，才能被右半查到； 3.touched必须撤销。和整体二分一样，兄弟分支要看到干净的数据结构。 「只撤销自己加过的」比「整棵树清零」快得多。
CDQ 的另一个大用途：动态问题静态化¶
「带修改的二维数点」是 CDQ 最常见的形态：
| 维度 | 内容 |
|---|---|
| 第一维 | 时间（操作序号）—— 天然有序，不用排 |
| 第二维 | 位置 —— CDQ 归并 |
| 第三维 | 值 —— 树状数组 |
CDQ 分治 = 用「分治」代替「一个维度的数据结构」。 树套树是「数据结构套数据结构」（\(O(\log^2 n)\)，常数巨大、空间大）； CDQ 是「分治套数据结构」（同样 \(O(\log^2 n)\)，但常数小、空间 \(O(n)\)）。 在 C++ 里这是压倒性优势；在 Python 里……见下节。
3 Python 的取舍¶
好消息：递归深度是安全的¶
| 算法 | 递归深度 | Python 判断 |
|---|---|---|
| DFS（链状图） | \(O(n)\) | ❌ 必须改迭代（DFS 深度优先搜索） |
| 递归线段树 | \(O(\log n)\)，但每次操作都递归 | ⚠️ 函数调用开销致命（线段树） |
| 归并分治 / CDQ / 整体二分 | \(O(\log n) \approx 17\) | ✅ 完全安全，不用 setrecursionlimit |
关键差别：线段树是「\(q\) 次操作 × 每次 \(O(\log n)\) 层递归」= \(q\log n\) 次函数调用； 分治是「一共 \(O(n)\) 次函数调用，每次做 \(O(\text{段长})\) 的工作」。 分治把函数调用开销摊薄了，这是它在 Python 里比递归线段树好得多的根本原因。
坏消息：merge 步骤是纯 Python 层循环¶
| 算法 | 每层的工作 | 总迭代数 |
|---|---|---|
| 归并求逆序对 | 一遍线性归并 | \(n\log n \approx 1.7\times10^6\)（\(n=10^5\)） |
| 整体二分 | 一遍元素塞入 + \(q\) 次树状数组查询 | \((n + 2q\log n)\log V \approx 1.2\times10^8\) |
| CDQ 三维偏序 | 一遍归并 + 每个元素一次树状数组操作 | \(n\log n\log V \approx 3.5\times10^7\) |
多出来的那个 \(\log\)（来自树状数组）就是分水岭。
实测数据（\(n = q = 10^5\)）¶
| 算法 | 实测耗时 | 判断 |
|---|---|---|
| 归并分治求逆序对 | 0.16 s | ✅ 稳 |
| 树状数组 + 离散化求逆序对 | 0.16 s | ✅ 打成平手 |
| CDQ 三维偏序（\(c\) 值域 \(2\times10^5\)） | 2.1 s | ⚠️ 险 |
| 整体二分（静态区间第 \(k\) 小） | 3.0 s | ⚠️ 险 |
| 树套树（线段树套线段树） | \(10^8\) 量级 | ❌ 完全不可行 |
| 主席树（可持久化线段树） | 建树 \(n\log n\) 个节点 = \(1.7\times10^6\) 个 Python 对象/数组格 | ❌ 内存与常数双杀 |
诚实结论：
场景 Python 判断 只需要「统计满足偏序的对数」（二维） ✅ 用树状数组，不要写分治 三维偏序，\(n \le 10^5\)，时限 \(\ge\) 5 秒 ⚠️ CDQ 可以试，2 秒左右 三维偏序，\(n \le 10^5\)，时限 2 秒 ❌ 区间第 \(k\) 小（静态），\(n=q\le10^5\)，时限 \(\ge\) 5 秒 ⚠️ 整体二分 3 秒 区间第 \(k\) 小（静态），可以离线且值域小 ✅ 改「分块 + 块内排序副本 + bisect」，见 平衡树与有序集合带修区间第 \(k\) 小，\(n=q\ge10^5\) ❌ Python 放弃 任何需要主席树 / 树套树的题 ❌
什么时候该把分治换成树状数组离线¶
判断标准：需要「跨中线的复杂逻辑」吗？
| 需求 | 用什么 | 理由 |
|---|---|---|
| 统计二维偏序对数 | 树状数组 + 排序 | 一遍扫描，没有递归、没有切片 |
| 离线区间查询（莫队式） | 排序 + 扫描 + 树状数组 | 同上 |
| 三维偏序 | CDQ（没有更好的选择） | 树状数组只能管一维 |
| 带修 + 多维 | CDQ | 分治是唯一能「消掉时间维」的手段 |
归并时要做 bisect / 双指针 |
归并分治 | 树状数组表达不了 |
Python 的通用降级路线（按优先级）：
树套树 / 主席树 ❌ ↓ 降级 CDQ 分治 / 整体二分 ⚠️ 3 秒量级 ↓ 降级 分块 + 块内排序副本 + bisect ⚠️ 但常数全在 C 层 ↓ 降级 排序 + 树状数组（若能把维数降到 2） ✅ ↓ 降级 Counter / sorted / bisect 一遍扫 ✅ 最优每往下一级，都是把 Python 层循环换成 C 层操作。 这条链条是整个第十部分反复出现的主题。
三个实现层面的 Python 优化¶
| 优化 | 效果 |
|---|---|
ids[:mid-lo+1] 的切片 → 改成传 (lo, hi) 下标 + 全局数组 |
省掉 \(O(n\log n)\) 次列表分配 |
归并用 res.append → 预分配 res = [0]*len + 下标赋值 |
快 10–20% |
树状数组的 add/pre 内联进归并循环 |
省掉 \(n\log n\) 次函数调用，能快 30% |
| 整体二分的递归 → 显式栈 | 层数只有 17，收益有限，但少一层开销 |
4 例题¶
| 题号 | 题名 | 难度 | 题解 |
|---|---|---|---|
| BISHI72 | 中位数之和 | 较难 | 题解 |
BISHI72 中位数之和（较难）¶
给定长度 \(n\) 的二进制数组 \(a\)（元素为 0 或 1），\(k\) 为奇数。 求 \(a\) 的所有长度恰为 \(k\) 的子序列的中位数之和，对 \(P = 10^9+7\) 取模。 \(t \le 10^4\) 组，\(\sum n \le 2\times10^5\)。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 原题。
✅ 题解见
solutions/nowcoder/BISHI72/sol.py，已通过官方样例验证。
这题为什么放在分治章：因为它是一道「看着像分治，实际不用分治」的题， 而分辨这一点的能力比会写 CDQ 更值钱。
为什么会想到分治：「所有子序列的某个统计量之和」这种句式， 在很多题里确实要靠分治（比如「所有子区间的最大值之和」用单调栈或分治）。 而且「中位数」天然带着「排序 / 第 \(k\) 小」的味道，容易联想到整体二分。
为什么分治在这里是错的路：
| 尝试 | 问题 |
|---|---|
| 枚举子序列 | \(\binom{n}{k}\) 是天文数字 |
| 分治：按下标对半，统计跨中线的子序列 | 子序列不要求连续，「跨中线」不构成有意义的划分 |
| 整体二分：二分中位数的值 | 中位数只能是 0 或 1，值域只有两个点，二分毫无意义 |
| 0/1 转化 + 组合计数 | ✅ 正解 |
关键观察（两步）：
第一步：0/1 值下「求和 = 计数」。 中位数只能是 0 或 1，所以
第二步：中位数为 1 的判据。 长度 \(k\)（奇数）的 0/1 序列，排序后第 \(h = \frac{k+1}{2}\) 个是 1 \(\iff\) 序列里 1 的个数 \(\ge h\)。
于是设数组里有 \(c_1\) 个 1、\(c_0 = n - c_1\) 个 0：
（从 1 里挑 \(j\) 个、从 0 里挑 \(k-j\) 个；按位置计数，同值元素在不同下标算不同子序列，正合题意。）
验算样例：\(n=5, k=1\)，全是 1 → \(c_1=5, c_0=0, h=1\)，\(j=1\)： \(\binom{5}{1}\binom{0}{0} = 5\) ✓
import sys
P = 1000000007
def main() -> None:
data = sys.stdin.buffer.read().split()
t = int(data[0])
idx = 1 # 游标：t 之后紧接着是第一组数据
cases = [] # 先把所有组读完，才知道阶乘表要开多大
mx = 1 # 所有组里最大的 n
for _ in range(t):
n = int(data[idx]); k = int(data[idx + 1]); idx += 2
c1 = 0 # 本组里 1 的个数，数组本身不必存下来
for j in range(idx, idx + n):
if data[j] == b"1": # 与 bytes 直接比，省去 int() 转换
c1 += 1
idx += n
cases.append((n, k, c1))
if n > mx:
mx = n
fact = [1] * (mx + 1) # ★ 全局只建一次阶乘表
for i in range(2, mx + 1): # 从 2 起：0! 和 1! 都是 1，初值已对
fact[i] = fact[i - 1] * i % P
inv_fact = [1] * (mx + 1)
inv_fact[mx] = pow(fact[mx], P - 2, P) # 费马小定理求一次逆元
for i in range(mx, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % P # 再线性递推出全部逆阶乘
# 由 1/(i-1)! = (1/i!) * i，倒着推只花 O(n) 次乘法
def C(a: int, b: int) -> int:
if b < 0 or b > a:
return 0 # 越界统一返回 0，省掉一堆边界判断
return fact[a] * inv_fact[b] % P * inv_fact[a - b] % P
out = []
for n, k, c1 in cases:
c0 = n - c1 # 0 的个数
h = (k + 1) // 2 # 至少要有 h 个 1，中位数才是 1
s = 0
for j in range(h, min(k, c1) + 1): # j = 选中的 1 的个数，上界受 k 和 c1 双重限制
s += C(c1, j) * C(c0, k - j) % P # 从 1 里选 j 个、从 0 里选 k-j 个
out.append(str(s % P)) # 循环内不取模也行，最后统一归约一次
sys.stdout.write("\n".join(out) + "\n")
main()
复杂度：预处理 \(O(\max n)\) + 每组 \(O(k)\)，总 \(O(\max n + \sum n)\)。 注意这是线性的——比任何分治做法都好。
四个坑（来自题解记录）：
- 逐组重建阶乘表会退化成 \(O(t\cdot n)\)，\(t=10^4\) 时直接爆。 必须在最外层建一次表，表长取所有测试用例里最大的 \(n\)； → 所以要先把所有输入读完（本身就是一次「离线」！）；
- 求和上界是 \(\min(k, c_1)\)，下界还要满足 \(k-j \le c_0\) 即 \(j \ge k-c_0\)—— 统一用 \(\binom{x}{y}=0\ (y>x \text{ 或 } y<0)\) 兜住最省心；
- 中位数是排序后第 \(\frac{k+1}{2}\) 个（1-indexed），\(k\) 奇数时 \(h = (k+1)//2\)；
- 每组 \(n\) 可能很小但 \(t\) 很大，IO 必须整块读。
本题给出的判断口诀： 看到「所有子序列/子集的某统计量之和」，先问「值域有多小」。 值域只有 \(\{0,1\}\) 时，「求和」退化成「计数」， 而计数往往有闭形式的组合公式，比任何分治都快一个数量级。
这与 平衡树与有序集合 的「先看值域再选数据结构」是同一条原则： 值域是解题时最该先找的那个数。
组合数取模的完整技术见 组合数学。
想练手 CDQ 的话¶
| 想练 | 推荐题 | Python 可行性 |
|---|---|---|
| 归并分治求逆序对 | P1908 逆序对 | ✅ 树状数组也一样快 |
| 最近点对（归并分治） | P1429 平面最近点对 | ✅ \(n\le10^5\) |
| 三维偏序（CDQ） | P3810 陌上花开 | ⚠️ 2 秒左右，时限 1 秒则不行 |
| 整体二分（静态第 \(k\) 小） | P3834【模板】可持久化线段树 2 | ⚠️ 3 秒 |
| 带修区间第 \(k\) 小 | P2617 Dynamic Rankings | ❌ Python 无解 |
| CDQ 优化 DP | P4093 [HEOI2016] 序列 | ❌ |
| 分块替代方案 | P2801 教主的魔法 | ✅ 首选 |
5 本章速查¶
| 要点 | 结论 |
|---|---|
| 归并求逆序对的一行 | 从右半取元素时 cnt += nl - i |
| 稳定性的关键 | 归并比较用 <= 而不是 < |
| 归并分治的通用模式 | 递归两半 → 统计跨中线的对 → 按键归并 |
| 归并分治 vs 树状数组 | 二维偏序两者等价，\(n=10^5\) 都是 0.16 s；优先树状数组（无递归、无切片） |
| CDQ 是什么 | 用分治代替「一个维度的数据结构」 |
| CDQ 的三段式 | 第一维排序 → 第二维 CDQ → 第三维树状数组 |
| CDQ 不重不漏的原因 | 任一对 \((j,i)\) 恰好有一层让 \(j\) 在左半、\(i\) 在右半 |
| CDQ vs 归并分治 | 归并统计对称贡献；CDQ 统计单向贡献（前半修改 → 后半询问） |
| CDQ 的别名 | 按时间分治 |
| 三维偏序坑一 | 完全相同的三元组必须去重合并，用重数 w 补回 |
| 三维偏序坑二 | 归并比较用 <=（\(b\) 相等也满足偏序） |
| 三维偏序坑三 | touched 必须撤销（只撤自己加过的，别整树清零） |
| CDQ vs 树套树 | 同为 \(O(\log^2 n)\)，但 CDQ 常数小、空间 \(O(n)\) |
| 分治的递归深度 | \(O(\log n)\approx17\)，Python 完全安全 |
| 分治 vs 递归线段树 | 分治总共 \(O(n)\) 次函数调用；线段树是 \(q\log n\) 次 → 分治摊薄了调用开销 |
| 分治在 Python 的瓶颈 | merge 步骤的 Python 层逐元素循环 |
| 分水岭 | 每层只有一遍线性扫描（✅）vs 每层还多一个 \(\log\)（⚠️） |
| Python 降级路线 | 树套树/主席树 ❌ → CDQ/整体二分 ⚠️ → 分块 + bisect → 排序 + 树状数组 ✅ → 一遍扫 ✅ |
| 最重要的取舍结论 | \(O(\sqrt n)\) 的 C 层操作常常打得过 \(O(\log^2 n)\) 的 Python 层操作 |
| BISHI72 的口诀 | 「所有子序列的统计量之和」→ 先看值域；值域 \(\{0,1\}\) 时求和 = 计数 = 组合公式 |
| 数据规模 → Python 现实性 |
|---|
| 归并分治求逆序对，\(n\le10^5\) |
| 归并分治求逆序对，\(n\le10^6\) |
| 树状数组 + 离散化求逆序对，\(n\le10^5\) |
| 最近点对（归并分治），\(n\le10^5\) |
| CDQ 三维偏序，\(n\le10^5\) |
| 树套树（线段树套线段树），\(n\ge10^5\) |
| 主席树，\(n\ge10^5\) |
| BISHI72 组合计数，\(\sum n\le2\times10^5\) |
整体二分的速查条目在 整体二分 章末。