CDQ 分治 - 洛谷保存站

> [%%% 陈丹琦](https://www.sohu.com/a/454907115_629135)

普通分治中，从大问题划分出来的所有子问题都是互不相关的，每个子问题只解决它自己。而 cdq 分治主要解决那些前一个子问题对后一个子问题有一定影响的问题。

举个例子：现在有若干个操作，每个操作是查询或者修改。每个修改操作都独立对询问产生影响。

如果直接对于每个询问分别处理，我们对于每个询问很可能要遍历之前所有修改。

比如操作 $1-5$ 为修改， $6$ 为询问， $7$ 为修改， $8$ 为询问。对于询问 $6$ ，我们要把 $1-5$ 的修改操作遍历一遍，而对于询问 $8$，我们要把 $1-5$ 和 $7$ 的修改操作一起遍历一遍。这样复杂度就退化成了 $O(n^2)$。

而这时候我们发现 $1-5$ 修改的遍历其实是冗余的。$1-5$ 遍历后既能更新询问 $6$ 的答案，也能更新询问 $8$ 的答案。之后我们只用用修改 $7$ 去更新询问 $8$即可。

为了更直观和保证优秀的复杂度。我们每次将所有操作 $[l,r]$ 进行折半。用 $[l,mid]$ 的所有修改去更新 $[mid+1,r]$ 的所有询问，再递归分别处理左右两部分。这样至多递归 $log$ 层。

注意：拿若干个修改一起更新若干个询问，肯定不优于拿若干个修改更新一个询问。但一般会有比 $O(n^2)$ 更优复杂度的办法。如树状数组，排序再双指针等等。

例题：[Ayuの天使玩偶](https://www.luogu.com.cn/problem/P4169)

***

CDQ 分治解决三维偏序：

设每个元素有三个属性为 $x,y,z$。对于每个元素 $i$， 求出满足 $x_j \le x_i,  y_j \le y_i, z_j \le z_i$ 的元素个数。

先按 $x$ 为第一关键字，$y$ 为第二关键字, $z$ 为第三关键字排序。这样，比任意一个元素小（三个属性都小于等于）的元素只可能在它前面。（注意：这里三个元素全部相等的情况需要特殊处理。）

我们就可以直接 cdq 分治。对于 $[l,mid]$ 与 $[mid+1,r]$ 分别按 $y$ 为第一关键字排序。双指针 $ll,rr$ 分别扫左右两个区间。这样我们可以时刻保证 $y_{ll} < y_{rr}$ ，不断将 $z_{ll}$ 放进树状数组中，查询 $z_{rr}$ 的前缀和即可

例题：[模板：三维偏序](https://www.luogu.com.cn/problem/P3810)

更多应用：[CDQ 分治2](https://www.luogu.com.cn/blog/lgzhou/cdq-fen-zhi-2-post)

正在渲染内容...