CDQ 分治看了很多次都没学明白，现在学明白了写个博客。

概念

CDQ 分治，旨在处理一系列序列上的统计问题。

序列中，如果特定的元素对之间存在贡献，那么我们可以考虑 CDQ 分治。

具体地，CDQ 分治是这样的：

  • 假设当前在处理 $[l,r]$ 区间内互相的贡献。
  • 令 $m=\lfloor\frac{l+r}{2}\rfloor$，把这个区间分成两部分：$[l,m]$ 和 $[m+1,r]$。
  • 递归处理 $[l,m]$ 和 $[m+1,r]$ 区间内的贡献。
  • 处理 $[l,m]$ 与 $[m+1,r]$ 之间的贡献。

可以看到，这样就能处理每一对之间的贡献。

那么到底是怎么做的呢？？

三维偏序

有 $n$ 个元素，每个元素有属性 $a_i,b_i,c_i$。求有序对 $(i,j)$ 满足 $a_i\leq a_j,b_i\leq b_j,c_i\leq c_j$ 且 $i\neq j$的数量，元素互异，$a_i,b_i,c_i\leq2\times 10^5$。

不妨先以 $a_i$ 为关键字升序排序，现在条件就变成了 $i\leq j,b_i\leq b_j,c_i\leq c_j$ 且 $i\neq j$，然后直接上 CDQ。

CDQ 的时候，当我们处理完一段区间 $[l,r]$，我们就把这段区间按照 $b_i$ 为关键字重新排序。

此时当我们处理 $[l,m]$ 与 $[m+1,r]$ 之间的贡献时，因为这两段区间刚返回过来，所以我们能保证两件事情：

  1. 对于 $\forall i\in[l,m],j\in[m+1,r],a_i<a_j$（因为我们早就按照 $a$ 排过序了，而这两段段内排序又不会影响到互相之间的 $a$）。
  2. 两段内的 $b$ 分别单调递增。

我们开一个值域大小的树状数组，再用双指针按照 $b$ 单增扫描这两端区间。每扫描到一个左边区间的下标 $i$，就在树状数组上把 $c_i$ 的地方增加 $1$；每扫描到一个右边区间的下标 $j$，就在树状数组上查询 $[1,c_j]$ 的和，累加进答案里。

这么做显然是对的。时间复杂度的话，递归深度是 $O(\log n)$，每层会遍历 $O(n)$ 个元素，每遍历一个元素需要 $O(\log n)$ 的操作，所以总复杂度是 $O(n\log^2 n)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void cdq(int l,int r){
    if(l==r)return;
    int m=(l+r)>>1;
    cdq(l,m);
    cdq(m+1,r);
    int pl=l;
    for(int i=m+1;i<=r;i++){
        while(pl<=m&&p[pl].b<=p[i].b){
            add(p[pl].c,p[pl].cnt);
            pl++;
        }
        f[p[i].id]+=ask(p[i].c);
    }
    for(int i=l;i<pl;i++)add(p[i].c,-p[i].cnt);
    sort(p+l,p+1+r,[](P x,P y){return x.b<y.b;});
}

当然，我们可以使用两层 CDQ（这个在四维偏序有用）。

具体地，当我们保证好上面两点后，给所有位于 $[l,m]$ 的元素打上标记，然后在 $[l,r]$ 按照 $b$ 升序排序，最后调用 CDQ2 函数，参数传进去 $[l,r]$。

那么我们如何实现 CDQ2？此时我们已经保证了 $b$ 升序，可是 $a$ 又乱了。但我们发现按照 $c$ 升序归并的过程中，之前的做过标记的点可以给之后没做过标记的点贡献。

所以我们 CDQ2 每次做完一个区间就把这个区间按照 $c$ 升序排序，这样当我们要统计这段区间互相的贡献的时候，我们能保证以下三点：

  1. 对于 $\forall i\in [l,m],j\in [m+1,r],b_i<b_j$（因为传进来的时候 $b$ 已经升序排好序了）。
  2. 两段内 $c$ 分别单调递增。
  3. 我们只需要统计左右之间有标记的点与没有标记的点相互之间的贡献。