CDQ分治的相关概念

CDQ 分治： CDQ 分治可以快速的解决一类问题：给定 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三种属性。对于每个 $i$，求一下满足 $a_j \leq a_i,b_j \leq b_i, c_j \leq c_i, j \neq i$ 的 $j$ 的数量。这种问题也被称为三维偏序问题

对于所有可以用 CDQ 分治解决的问题，都是将原问题转化成以上这个三维偏序问题。

CDQ 分治的思想：

我们先考虑简化版的问题，然后依次扩展到三维。

对于一维问题，就是对于每个 $i$，找出有多少不同的 $j$ 满足 $a_j \leq a_i,i \neq j$。

这里为了方便，我们先假定所有 $a_i \neq a_j$，后面再考虑如何处理 $a_i=a_j$ 的情况，并且所有下标都从 $1$ 开始。

对于一维版本我们只需要将所有元素按照 $a$ 从小到大排序，对于每个元素 $a_i$ 来说，所有 $< a_i$ 的数全部在 $a_i$ 的左边。因此一共会有 $i-1$ 个 $j$ 满足 $a_j \leq a_i$。

然后考虑二维版本，二维版本就是再加上一个 $b_j \leq b_i$ 的条件。二维的做法很多，一种做法就是将所有元素按照双关键字从小到大排序，也就是按 $a$ 排序，如果 $a$ 相同则按照 $b$ 排序。此时对于每个元素 $a_i$，所有满足 $a_j \leq a_i,b_j \leq b_i$ 的元素一定在 $a_i$ 的 前面，但不代表前面所有元素都满足条件，因此可以从前往后扫描一遍，首先前面的元素一定满足 $a_j \leq a_i$，所以我们只需要找一下前面有多少个 $j$，满足 $b_j \leq b_i$。这里可以用很多方法求，一种比较简单的方法是树状数组，我们可以先将 $b$ 数组离散化，然后从前往后枚举，对于 $i$ 求一下 $1 \sim b_i$ 中出现了多少个数，就是满足条件的 $j$ 的数量，然后记得将 $b_i$ 加入树状数组。

这里除了树状数组以外，也可以用分治来求二维版本，第一步还是将所有元素按照双关键字排序，这里双关键字排序的作用是能保证对于每个 $i$，满足要求的元素一定在前面，不可能出现在后面。然后同样是要求对于每个 $i$，前面有多少个 $b_j \leq b_i$，此时区间中所有满足要求的 $i,j$ 对有三种情况，一种是 $i$ 和 $j$ 都在左半边，一种是 $i$ 和 $j$ 都在右半边，一种是 $i$ 和 $j$ 一个在左半边一个在右半边。由于我们已经将所有元素按照双关键字排好序，因此此时所有满足条件的 $i,j$ 对都已经是 $j$ 在 $i$ 的左边。对于情况一，我们可以递归到左区间去处理。对于情况二，我们可以递归到右区间去处理。对于情况三，由于一定是 $j$ 在左，$i$ 在右，而且此时左边的元素的 $a$ 都一定 $\leq$ 右边的元素的 $a$，因此我们只需要对于右半边的每个 $i$ 求一下左半边有多少个 $j$ 是满足 $b_j \leq b_i$。这里可以用归并的思想，我们在递归的过程中用归并将所有元素按照 $b$ 来排序，此时对于当前区间，左半区间和右半区间就已经各自排好序了，那么此时对于每个 $i$ 要想求有多少个 $j$ 满足 $b_j \leq b_i$，就可以用双指针扫描来求，每次 $i$ 向后移动一格，然后将 $j$ 向后移动找到第一个 $b_j > b_i$ 的位置，此时满足 $b_j \leq b_i$ 的 $j$ 就有 $j-1$ 个。由于两个区间都各自有序，因此 $i$ 递增之后，$j$ 也一定是递增的。就可以直接扫描。

然后考虑三维版本，也就是最终版本。此时需要满足 $a_j \leq a_i,b_j \leq b_i,c_j \leq c_i$ 三个条件。这里同样可以用类似上面的做法，我们将所有元素按照三关键字从小到大排序，也就是先按照 $a$ 排序，$a$ 相同按照 $b$ 排序，$b$ 相同按照 $c$ 排序。此时同样保证对于每个 $i$，所有满足要求的 $j$ 一定在 $i$ 的左边。然后我们也用分治的思想来做。将所有满足要求的 $i,j$ 对分成三大类。第一类是 $i,j$ 都在左半边，第二类是 $i,j$ 都在右半边，第三类是 $j$ 在左，$i$ 在右。第一类和第二类都可以用递归来求。只需要考虑第三类，首先因为按照三关键字排序，所以左侧任意元素 $a_j$ 一定 $\leq$ 右侧任意元素 $a_i$。然后只需要考虑后面两个条件，对于 $b_j \leq b_i$，我们可以用二维的方法，在归并的过程中将所有元素按照 $b$ 重新排序，此时对于右侧任意一个 $i$，我们要求出左侧有多少个 $j$ 满足 $b_j \leq b_i,c_j \leq c_i$，$b$ 的限制我们可以用双指针来解决。对于每个 $i$ 我们都能用双指针线性的找到第一个 $b_j > b_i$ 的位置 $j$，此时 $1 \sim j-1$ 中的所有元素都一定满足 $b$ 限制，然后我们需要在 $1 \sim j-1$ 中找到满足 $c$ 限制的数的个数。这里就可以用到二维版本的第一个做法，用树状数组来求，我们将 $c$ 数组离散化，此时从前往后对于每个 $i$ 来说，$\leq c_i$ 的数的个数就相当于 $1 \sim c_i$ 的出现的数的个数，而每次 $j$ 往后移动一个，相当于往树状数组中加入一个数，很好维护。

到此，我们就将三维偏序问题解决了，第一维通过三关键字排序自然满足，第二维通过双指针来求，第三维通过树状数组来求。时间复杂度的话，首先需要一个分治的递归，一共 $\log n$ 层，每一层中在进行线性的双指针的同时还要维护树状数组，因此整个的时间复杂度就是 $n\log^2n$

然后这里还有一个特殊情况，如果存在 $a_j=a_i,b_j=b_i,c_j=c_i$ 这样的完全相等的两个元素，则按照三关键字排序后这两个元素一定挨在一起，对于后一个元素是可以正确求解的，但是对于前一个元素，由于我们只考虑前面的元素不考虑后面的元素，所以对于前一个元素就会把和他相等的元素漏掉。因此我们需要特殊处理一下，将所有完全相等的元素判个重去除掉，然后对于每个元素我们再计个数，表示这个元素出现多少次。这样就能保证所有元素都不同的。然后在求完三维偏序之后，我们再将所有相同的情况加上即可，如果对于 $a_i$ 一共有 $k$ 个，那么对于 $a_i$ 满足条件的数还需要再加上 $k-1$，这样就将所有情况都考虑完整了。