cdq 分治是用于解决二维偏序的分治算法（因为 N 维偏序可以通过排序钦定第一维的顺序，所以 N 维偏序等价于求新序列的 N-1 维偏序）。

对于序列 $(a,b)$ 的二维偏序 $(a_i,b_i)\preccurlyeq (a_j,b_j)$，分为三部分统计：

• $[l,mid],i,j\in [l,mid]$，递归左区间
• $[mid+1,r],i,j\in [mid+1,r]$，递归右区间
• $i\in [l,mid],j\in [mid+1,r]$，遍历左/右区间，使用数据结构维护另一个区间的贡献

点击展开代码

void cdq(int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    int now = l;
    for (int i = mid + 1; i <= r; i++) {
        while (now <= mid && a[now].a <= a[i].a) {
            // 第一维 已升序，维护 第二维 的贡献
            now++;
        }
        // 计算 i 的答案
    }
    for (int i = l; i < now; i++){
        // 删除 [l, now] 的贡献
    }

    // 归并 第一维 升序
    int cnt = 0;
    now = mid + 1;
    for (int i = l; i <= mid; i++) {
        while (now <= r && a[now].a <= a[i].a) {
            A[++cnt] = a[now];
            now++;
        }
        A[++cnt] = a[i];
    }
    while (now <= r) {
        A[++cnt] = a[now];
        now++;
    }
    for (int i = 1; i <= cnt; i++)
        a[l - 1 + i] = A[i];
}

时间复杂度

复杂度应按具体维数和每一层实际执行的操作分别计算。一次 CDQ 分治有 $O(\log n)$ 层；若同一层内所有元素只参与常数次扫描，则这一部分的总代价为 $O(n\log n)$。若扫描过程中还要对数据结构进行单次 $O(\log n)$ 的修改或查询，则总代价为 $O(n{\log }^{2}n)$。

例如，三维偏序通常先按第一维排序，用 CDQ 分治处理第二维的先后关系，并用树状数组维护第三维。CDQ 每层共处理 $O(n)$ 个元素，每个元素在树状数组上的操作为 $O(\log n)$，共有 $O(\log n)$ 层，因此总时间复杂度为 $O(n{\log }^{2}n)$。对于常见的固定 $N$ 维偏序实现，每增加一个需要递归分治或由数据结构维护的维度，通常再增加一个对数因子，因而写作 $O(n{\log }^{N-1}n)$；

实际竞赛中还应结合常数判断实现是否可行：维数升高后，多层分治和数据结构操作的常数较大，理论上优于 $O(n^2)$ 的实现未必在给定数据范围内更快。

重复点与等号

处理偏序前必须先明确各维使用严格小于还是小于等于。对于各维均采用“$\le$”的非严格偏序，完全相同的点会互相产生贡献；若它们被直接分到 CDQ 的两侧，可能只统计到其中一个方向，使相同点得到不一致的答案。常用做法是先将完全相同的点合并为一个结点并记录出现次数 cnt，修改数据结构时加入 cnt。设从其他点组得到的贡献为 ans，若答案不计自身，则该组中每个原点的答案为 ans + cnt - 1；若计入自身，则为 ans + cnt。

若某一维要求严格小于，或相等坐标之间不应产生贡献，则同坐标事件需要成组处理：先完成这一组的查询，再统一执行修改，避免组内元素相互贡献。排序规则、归并时使用的 < 或 <=，以及数据结构查询的边界必须采用同一套等号约定。