CDQ分治学习笔记

· · 个人记录

Part 0：前言

今天学长讲了一下CDQ分治，但是他讲课的时候我迟到了整整40分钟，于是自学了一个下午，翻了几十篇题解，终于浅显地搞懂了这个离线算法。

其实我感觉网上的题解讲的都不是很清楚，于是想自己写一篇。

文章同步于CSDN

码字不易，点个赞吧。

Part 1：前置知识

先摆上模板题

在看这题之前，我们看另外一道非常简单的问题：戳。

这道题题意就是让我们求一个数列的逆序对的数量，如果你写过用树状数组的做法，这个部分可以直接跳过。

首先这题树状数组是可以做的，但是作者并不会树状数组，所以其实可以用线段树，因为线段树的功能是比树状数组强大很多的。

那么逆序对的数量怎么求呢？

我们只需要遍历一遍数组，接着对于每一个数，求在它前面且比它的值更大的数有多少个，最后再把它们加起来即可。

于是，我们可以考虑根据值来建线段树，初始线段树为全 0。现在按照序列从左到右将数据的值对应的位置的数加一，代表又有一个数出现。因此，在循环到第 i 项时，前 1 \sim (i-1) 项已经加入到线段树内了 , 线段树内比 a_i 大的都会与 a_i 构成逆序对，因为它们一定出现的更早，所以产生的逆序对数量为 i-query(a_i)

注意这里 a_i \le 10^9，线段树开不了那么大，所以要离散化，而且记得开 long long。

代码在这里：戳。

Part 2：CDQ分治

我们回到模板题。

我们可以考虑一下刚刚那个问题的实质是什么。

虽然那道题只给了我们一个值，但是每一个数还有一个自己对应的属性：自己的下标。所以，刚刚那道题可以称作一个“二维偏序”。

那么，对于三维偏序，我们怎么求它呢？

我们考虑一下：逆序对有几个求法？

第一种，是线段树（树状数组）；第二种，是分治算法。

那么，我们把这两种方法结合起来，是不是就能求三维偏序呢？

答案是可以的。

这就是“CDQ分治”。

第一部，我们先对所有元素按 a_i 排序。这样我们就可以保证我们在处理 a_i 的贡献是不用考虑 a_{i+1} \sim a_n 对 a_i 的贡献的。

这时候，我们对排序后所有的元素进行分治，在对 l \sim r 这个区间分治的时候，我们需要将所有的贡献分为3种情况:

我们假设 a_i 对 a_j 产生贡献，即 a_i \leq a_j 且 b_i \leq b_j 且 c_i \leq c_j。

先把代码放上来：

void cdq(int l, int r){
    if(l == r){
        return;
    }
    int mid = (l + r) >> 1; // 求区间中值
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(a + l, a + mid + 1, cmp0); // 这里cmp0是以b从小到大排序
    sort(a + mid + 1, a + r + 1, cmp0);
    // 在这个地方的i和j和上文的i和j是反的
    int j = l;
    for(int i = mid + 1; i <= r; i++){ // i遍历 (mid+1) ~ r
        while(j <= mid && a[j].y <= a[i].y){ // 这个循环保证b[j]一定小于b[i]
            update(a[j].z, a[j].cnt, 1); // a[j].cnt 表示 a[j] 有多少个重复的数，因为CDQ分治处理相同的数据时会出问题。
            j++;
        }
        a[i].ans += query(1, a[i].z, 1); // 我们查询有多少个c[j]是比c[i]小的，这样我们就能算出c[i]的答案要增加多少
    }
    for(int i = l; i < j; i++){
        update(a[i].z, -a[i].cnt, 1);
    } // 注意每次操作后一定要清空线段树，直接memset的复杂度太高了，于是我们采用了这么一种做法，把以前加了的值重新减回去。
}

首先，我们要先递归前两种情况，这个东西一定要放在第一位，原因等下会说。

其次，我们按照 b 从小到大排序。

这时候，很容易产生一个问题：按照 b 排序的话，那么 a 的顺序不会乱吗？

其实是不会的，因为我们是将前半部分和后半部分分别按 b 排序，而由于我们之前排过 a 的序，i 在左半部分，j 在右半部分，所以 a_i 一定小于 a_j。

所以这时候你明白了为什么要先执行第 1 和第 2 种情况了吧，因为如果我们先排序的话，先整体的按照 b 排序，势必会影响到局部的 a 的情况，而先按局部 b 排序，则不会影响到整体上 a 的相对大小。

那么我们现在已经处理完了前两维了，第三维只需要仿照逆序对的线段树（树状数组）方法去求即可。

如果你还不怎么清楚，可以往上翻看代码里的注释。

这里注意CDQ分治是不能处理元素相同的情况的，所以我们要预处理有多少个相同的元素，在计算共享的时候算上所有相同元素，而且相同元素之间也是有贡献的，所以最后计算答案的时候要记得加上。

那么CDQ分治的主要部分就这些了，模板题的AC代码放到剪切板里了，里面也有注释：戳

Part 3：结语

模板题本质上其实只是一个CDQ分治的一个简单的应用，而实际上CDQ分治只是一种分治上的思想，就是上文中所说的将一个集合分治后分为三类的思想，一般第一和第二种情况直接继续分治即可，而正真需要我们思考的是第三类的情况和情况时间怎么合并

Part 4：相似题目

不知道，博主自己一题没做。