CDQ 分治是一种离线算法框架，通过"分治 + 归并"的思想，将三维偏序等复杂计数问题降维处理，时间复杂度 O(n log²n)。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph TD A[按维排序] --> B[分两半] B --> C[左半求解] B --> D[右半求解] C --> E[合并: 左对右贡献] D --> E
普通分治：将问题分成两半，分别求解，合并。 CDQ 分治：将问题按某一维排序后分成两半，左半对右半的贡献在合并时计算。
关键区别：CDQ 关注的是"左半部分对右半部分的影响"，而非简单的子问题合并。
二、三维偏序问题
给定 n 个三元组 (aᵢ, bᵢ, cᵢ)，对每个 i 求满足 aⱼ ≤ aᵢ, bⱼ ≤ bᵢ, cⱼ ≤ cᵢ 的 j 的个数。
思路
- 第一维：排序（预处理）
- 第二维：CDQ 分治时归并排序
- 第三维：树状数组
// 三维偏序模板
void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid + 1, r);
// 归并：按 b 排序，左半对右半的贡献
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (arr[i].b <= arr[j].b) {
bit.add(arr[i].c, 1); // 左半元素加入 BIT
tmp[k++] = arr[i++];
} else {
ans[arr[j].id] += bit.query(arr[j].c); // 查询 ≤ c 的个数
tmp[k++] = arr[j++];
}
}
while (i <= mid) tmp[k++] = arr[i++];
while (j <= r) {
ans[arr[j].id] += bit.query(arr[j].c);
tmp[k++] = arr[j++];
}
// 清除 BIT
for (int p = l; p <= mid; p++) bit.add(arr[p].c, -1);
// 回写（归并排序）
System.arraycopy(tmp, 0, arr, l, k);
}