CDQ 分治学习笔记

简介

CDQ 分治一般用来解决偏序问题。我们先来回忆一下：

• 一维偏序：排序即可解决问题。
• 二维偏序：对于 \((a,b)\)，我们使用排序解决 \(a\)，然后 \(b\) 使用树状数组即可简单维护。
• 三位偏序：有一维不好处理，怎么做呢?

这时候，CDQ 分治即使一个不错的解决方法。在允许离线的情况下，CDQ 可以在 \(O(n\log^2n)\) 的复杂度内解决三维偏序。

其实，我们有一个简单的解决方法：排序，然后使用二维数据结构解决二维剩下的偏序问题。但是鉴于那样的数据结构相对更为复杂、代码复杂度更高，所以 CDQ 还是很不错的。

算法

我们使用排序解决第一维，一维数据结构（比如树状数组）解决第三维。然后第二维，我们使用分治算法解决。具体来说：

对于一个区间 \((l,r)\)，我们将其分为 \((l,mid)+(mid+1,r)\)，然后递归计算两个区间的贡献，再计算两个区间之间的贡献（其实类似于线段树的思路）。假如两个子区间的贡献已经搞定了，那我们此时只需要计算左区间对于右区间的贡献。此时，我们左区间每个数可以理解为 \((0,b,c)\)，右边则是 \((1,b,c)\)——此时，相当于转换为二维偏序。因此，我们可以使用排序加上树状数组解决。具体来说，我们使用归并排序，遇到左区间的数就加入数据结构，遇到右区间的数就查询数据结构。这样即可在 \(O(len\log len)\) 的复杂度内解决某一个区间中单独的贡献，然后总的复杂度就是 \(O(n\log^2 n)\)。

我们来分析一下这个算法的本质。为什么只用一个简单的分治，即可解决需要用高级数据结构才能解决的问题呢？我的理解，就是降维——高维问题转换为低维问题。我们原本是一个 \(O(n)\) 规模的三维问题，然后用一个分治将其转换为了一个 \(O(n\log n)\) 的二维问题——这个就是精髓。非常奇妙。

那么现在，我们来尝试解决一下四维偏序——虽然没有什么实际用处，但是可以加深理解。

P3769 [CH弱省胡策R2]TATT

我们有一个简单的做法：排序，然后用三维数据结构解决剩下的三维。这个当然是可行的，只需要一个 KD-Tree 即可，也不失为一种优秀的做法。

或者，一维排序然后数据结构套数据结构（树状数组+KD-Tree），也很优秀。

或者，一维排序一维 CDQ，剩下的使用二维数据结构——可行，但是应该既不好写又不优秀。

甚至，你可以直接使用 KD-Tree 解决四维偏序，只不过复杂度巨大无比而已。

而当然，CDQ 是可行的。我们排序一维，一维数据结构搞定一维，中间两维都使用 CDQ。

我们先排序然后第一层分治，问题转换为：前一半子区间 \((0,b,c,d)\) 对于后一半子区间 \((1,b,c,d)\) 的贡献。注意，我们需要计算这个区间第一维所有 \(0\) 对于 \(1\) 的贡献。

然后对于这一个区间，按照 \(b\) 排序。然后接着分治下去。接下来，问题就转换为 \((0,0,c,d)\) 对于 \((1,1,c,d)\) 的贡献。然后就使用二维的方法解决即可。

复杂度的话考虑一个位置会被操作 \(O(\log^2)\) 次，加上数据结构总共就是 \(O(n\log^3n)\)，但是常数很小。

非常有意思。