CDQ 分治：在高维偏序中制造可统计的秩序

核心洞察：CDQ 分治的力量不在“多一种模板”，而在于它主动创造了一个方向已确定、另一个方向可查询的局部秩序。 设有许多点，每个点带三维坐标 $`(a, b, c)`$，需要统计满足 $`a_j \le a_i, b_j \le b_i, c_j \le c_i`$ 的点对。暴力枚举需要三重比较；仅按一个维度排序，又无法同时保证另外两个维度的贡献关系。

先把一个维度交给递归

将点按 a 排序后，CDQ 在下标区间上分治。处理左半边与右半边的交叉贡献时，左边的点天然拥有不大于右边的 a；第一个维度已经被递归边界固定。 接下来按 b 做归并。扫描过程中，左侧 b 不大于当前右侧点的元素被加入 Fenwick Tree，树状数组维护它们在 c 维上的数量。于是查询前缀和即可得到第三维也满足条件的贡献。

while (i <= mid && j <= right) {
    if (points[i].b <= points[j].b) {
        bit.add(points[i].c, points[i].count);
        ++i;
    } else {
        points[j].answer += bit.sum(points[j].c);
        ++j;
    }
}

这里的关键不只是代码顺序，而是语义：左边是已经发生、可以贡献的点；右边是正在提问、等待累计答案的点。

为什么要合并重复点

完全相同的三维坐标互相满足偏序。如果逐个处理，不仅会重复做工作，还容易把同坐标的先后顺序错误地计数。应先排序并合并相同点，用 count 表示出现次数，最后再把总答案按次数还原。

三种工具各做一件事