第97课：CDQ分治

学习目标

理解CDQ分治的基本思想与分治策略。
掌握使用CDQ分治解决三维偏序问题的标准流程。
了解CDQ分治作为一种“离线算法”的优势与应用场景。
能够将CDQ分治与树状数组/线段树等数据结构结合使用。
比较CDQ分治与“树套树”等在线方法的异同与适用场景。

核心概念

1. CDQ分治是什么？

CDQ分治是一种基于分治思想的算法，由陈丹琦（CDQ）在其论文中首次系统阐述。它主要用于处理离线的、具有可合并性质的查询问题，尤其擅长降维（将多维问题转化为低维问题）。

你可以把它理解为一种“带脑子”的归并排序。在归并排序的合并步骤中，我们不仅能排好序，还能顺便计算出左边序列对右边序列的贡献。这种“在分治的过程中完成统计”的思想，是CDQ分治的核心。

2. 经典问题：三维偏序

问题：给定 n 个点 (xi, yi, zi)，对于每个点 i，求满足 xj <= xi, yj <= yi, zj <= zi 且 j != i 的点 j 的数量。这就是著名的三维偏序问题，也是学习CDQ分治的绝佳入口。

为什么三维难处理？ 对于一维偏序（例如 xj <= xi），排序后扫一遍即可。对于二维偏序（xj <= xi 且 yj <= yi），可以按 x 排序，然后对 y 建立树状数组，用类似“逆序对”的思想在 O(nlogn) 内解决。

三维呢？如果暴力枚举，时间复杂度是 O(n^2)。使用“树套树”（例如树状数组套线段树）可以在 O(n log^2 n) 时间内在线回答查询，但实现复杂，常数较大。而CDQ分治提供了一种更优雅、代码更简洁的离线解决方案，时间复杂度同样为 O(n log^2 n)。

CDQ分治解决三维偏序的思路：

排序（降第一维）：首先，将所有点按第一维 x 从小到大排序。这样，在后续处理中，当我们考虑左半区间 L 和右半区间 R 时，所有 L 中的点的 x 值必然都小于等于 R 中的点的 x 值。这一维的偏序条件被排序“固化”了。
分治与归并（降第二维）：类似归并排序，在 solve(l, r) 函数中：
- 如果 l == r，直接返回。
- 递归处理 solve(l, mid) 和 solve(mid+1, r)。
- 关键的“CDQ”步骤：此时，左半区间 [l, mid] 和右半区间 [mid+1, r] 内部的贡献已经由递归计算完毕。现在需要计算的是：左半区间中的点对右半区间中的点的贡献。
- 我们将两个子区间分别按第二维 y 从小到大排序（或使用归并的思想在合并时按 y 排序）。
- 然后用一个双指针扫描这两个有序序列。对于右区间中的每个点 j（其 y 值为 yj），将左区间中所有 y 值 <= yj 的点的第三维 z 的值，加入到一个数据结构中（通常使用树状数组）。
- 接着，在树状数组中查询 zj 这个值的前缀和，这个结果就是满足 x 条件（由排序保证）和 y 条件（由扫描保证）且 z <= zj 的左区间的点的数量。这个数量就是左区间对点 j 的贡献。
- 最后，在离开当前递归层之前，记得清空树状数组，以避免对其他层造成干扰。
树状数组（降第三维）：树状数组（BIT）用于在合并步骤中，高效地维护第三维 z 的信息。它支持单点修改和前缀查询，正好对应“添加一个点的 z”和“查询 z 值小于等于某个值的点的数量”。

总结一下：排序降一维，分治归并降一维，树状数组降一维。三步“降维打击”，将三维问题解决。

代码示例

以下代码使用CDQ分治解决一个经典的带修改的三维偏序问题（P3810 【模板】三维偏序（陌上花开））。问题简述：有 n 朵花，每朵花有三个属性 (a, b, c)。定义花 i 在花 j 的下方，当且仅当 a_i <= a_j, b_i <= b_j, c_i <= c_j。求对于每种花 k，有多少种花在其下方。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005; // 根据题目数据范围调整
const int MAXK = 200005; // c的值域，可能需要离散化

struct Flower {
    int a, b, c, cnt, res; // cnt: 与它完全相同的花的数量；res: 答案
    // 为了去重和排序，还需要一个标识
    bool operator==(const Flower& other) const {
        return a == other.a && b == other.b && c == other.c;
    }
};

Flower flowers[MAXN], tmp[MAXN];
int bit[MAXK], ans[MAXN]; // ans[i] 表示有多少种花在它下面

// 树状数组操作
void update(int i, int val) {
    for (; i <= MAXK; i += i & -i) {
        bit[i] += val;
    }
}
int query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & -i) {
        sum += bit[i];
    }
    return sum;
}

// CDQ分治核心函数
void solve(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    solve(l, mid);
    solve(mid+1, r);

    // 归并排序第二维 b
    int i = l, j = mid+1, k = l;
    while (i <= mid && j <= r) {
        if (flowers[i].b <= flowers[j].b) {
            // 左区间的点 b 值小，将其 c 值加入树状数组
            update(flowers[i].c, flowers[i].cnt);
            tmp[k++] = flowers[i++];
        } else {
            // 右区间的点 b 值小，查询其 c 值的前缀和（即左区间中 b<=它的点的数量）
            flowers[j].res += query(flowers[j].c);
            tmp[k++] = flowers[j++];
        }
    }
    // 处理剩余元素
    while (j <= r) {
        flowers[j].res += query(flowers[j].c);
        tmp[k++] = flowers[j++];
    }
    // 注意：左区间剩余的点只是没有参与贡献，但它们已经被加入树状数组，需要在后面清理。
    // 复制回原数组
    for (i = l; i < k; ++i) flowers[i] = tmp[i];
    // **非常重要：清理树状数组**，避免影响上层递归或后续计算
    for (i = l; i <= mid; ++i) {
        update(flowers[i].c, -flowers[i].cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k; // n: 花的总朵数, k: 值域（用于树状数组）
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> flowers[i].a >> flowers[i].b >> flowers[i].c;
        flowers[i].cnt = 1; // 初始计数为1
    }

    // 1. 排序第一维 a，并合并完全相同的花
    sort(flowers + 1, flowers + n + 1, [](const Flower& x, const Flower& 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;
    });

    int m = 1; // 去重后的花的数量
    for (int i = 2; i <= n; ++i) {
        if (flowers[i] == flowers[m]) {
            flowers[m].cnt++;
        } else {
            flowers[++m] = flowers[i];
        }
    }

    // 2. CDQ分治处理
    solve(1, m);

    // 3. 统计答案
    // res[i] 表示在它下面（不包含它自己）的花的数量
    // 但题目要求“有多少种花在其下方”，包含与它相同属性的花（如果数量>1）
    // 所以最终答案为 res[i] + cnt[i] - 1
    for (int i = 1; i <= m; ++i) {
        ans[flowers[i].res + flowers[i].cnt - 1] += flowers[i].cnt;
    }
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

代码解析：

结构体与去重：首先按 a, b, c 排序，并将完全相同的花合并，记录其数量 cnt。这是为了处理“有多少种花”的问题。
分治过程：solve(l, r) 是核心。递归处理左右子区间后，将两个子区间按 b 值归并。在归并过程中，每当一个左区间的点被放入临时数组时，我们就把它的 c 值“贡献”到树状数组中。每当一个右区间的点被放入时，我们就查询树状数组中 <= c 的数量，作为它获得的贡献。
清理操作：归并完成后，必须将左区间点对树状数组的影响清除，以保证算法的正确性。
复杂度：排序 O(nlogn)，分治过程中每一层归并的总复杂度为 O(nlogk)，共 logn 层，总复杂度 O(nlognlogk)。

实践练习

练习1：二维偏序（巩固基础）

问题：给定 n 个点 (xi, yi)，求每个点左下方（xj <= xi 且 yj <= yi）的点的数量。要求：尝试用CDQ分治的思路解决它（提示：这相当于第三维 z 为常数或忽略的特例，可以看作二维问题，CDQ分治只需降一维）。 预期输出：对于输入 n=3, points={(1,1), (2,2), (1,2)}，输出应为 0, 2, 1。

练习2：带修改的二维偏序（进阶）

问题：有 n 个操作，有两种类型：

(1, x, y)：在平面上添加一个点 (x, y)。
(2, x1, y1, x2, y2)：查询矩形 (x1, y1) 到 (x2, y2) 内点的数量。所有操作按时间顺序给出。要求离线处理所有查询。要求：使用CDQ分治，将时间作为第一维，操作/查询作为点或事件。 预期输出：对于操作序列 [(1,1,1), (1,2,2), (2,0,0,3,3), (1,1,3), (2,0,0,2,2)]，查询结果应为 2, 2。

练习3：三维偏序（挑战）

问题：洛谷 P3810 【模板】三维偏序（陌上花开）。要求：在理解示例代码后，尝试不看代码，独立实现CDQ分治求解此问题。 预期输出：通过题目所有测试用例。

常见错误

忘记清理树状数组：这是最致命、最常见的错误。在 solve 函数的归并结束后，必须用 update(c, -cnt) 的方式清除左区间点的影响。否则，树状数组中的数据会“污染”更高层的递归或并行分支，导致结果错误。
分治时比较条件写错：在归并按 b 排序时，要确保 <= 的方向正确，使得左区间贡献给右区间。写成 < 或方向搞反会导致漏算或多算。
三维排序/比较不完整：在最初排序第一维 a 时，如果只按 a 排序，当 a 相同时，b 和 c 的顺序是任意的。这可能会影响后续CDQ分治中按 b 归并的结果。因此，通常需要按 (a, b, c) 进行稳定的全排序，并处理相同的点。
树状数组值域考虑不周：树状数组的大小 MAXK 必须大于等于第三维 z 的最大值（或离散化后的最大值）。如果 z 值范围很大但 n 较小，需要先进行离散化。
递归出口处理不当：当 l == r 时直接返回，这是正确的。但要注意，如果区间内只有一个点，它不需要计算“左区间对右区间”的贡献，因为它自身就是左也是右。

小结

核心思想：CDQ分治是分治与归并排序思想的巧妙结合，其精髓在于在分治的“合并”阶段，统计左半部分对右半部分的贡献。
解决三维偏序的标准框架：
- 第一维：按此维排序（通常在最开始一次性完成）。
- 第二维：在CDQ分治的合并过程中，按此维进行归并排序。
- 第三维：在归并扫描时，使用树状数组维护此维信息，进行查询和更新。
离线算法的优势：CDQ分治是离线算法，它要求所有操作/查询事先知道。这使得它

练习编辑器

rust

CDQ 分治