基于时间的分治算法-CDQ分治

对于一些的数据结构题，我们可以把每个询问视为初始数据与询问之前的修改对这个询问所做的影响。

这样我们就可以高效的解决一些问题。

设$solve(l,r)$能够处理$l$~$r$内的操作，那么我们可以通过如下递归分治来解决：

递归计算$solve(l,mid)$
递归计算$solve(mid+1,r)$
计算左边的修改对右边的询问的影响

假设第三步的复杂度是$O(f(n))$，显然整个算法的复杂度就是$O(f(n)logn)$

比如说求逆序对的归并排序其实就是一种CDQ分治（我是这么想的）。

我看到一个描述挺清晰的CDQ讲解，如下：

CDQ分治

查询的限制——序

对于一个数据结构题而言（或者需要运用数据结构的地方），我们无非就是做两件操作，一是修改，二是查询
对于修改而言，有插入，删除，变更（其实等价于删除再插入）这几种方式
那么查询的本质是什么呢
我们思考所遇到过的数据结构题，可以发现查询实际上就在做一件事情：
把符合本次查询的限制的修改对答案产生的效果合并起来
满足这种限制通常表现为一种序的要求，并且这种序是广义的，符合限制的操作往往是按某种序（或多种序）排序后的操作的前缀
通常来说,查询一定有时间上的限制,也就是要求考虑发生在某个时刻之前的所有查询,对于一个问题而言,假如所有查询要求的发生时刻相同,那这就是一个静态查询问题,如果要求发生的时刻随着查询而变,那这就是一个动态修改问题,动态修改问题较静态查询而言复杂很多,往往需要高级数据结构,可持久化等手段,而静态查询简单很多,例如时间倒流,twopointers之类的方法都是很好的选择

动态修改->静态查询

CDQ分治算法的核心就在于:去掉时间的限制,将所有查询要求发生的时刻同化,化动态修改为静态查询
(其实对于有些问题来说可以把某一维的限制通过排序看作时间限制然后运用CDQ分治)
我们记过程$DivideConquer(l,r)$表示处理完$[l,r]$内的修改对查询的影响
此时我们引入分治思想,将操作序列划分为$[l,mid]$,$[mid+1,r]$两个区间
这两个区间内部的修改对区间内部的查询的影响是完全相同的子问题,我们递归处理
处理完之后剩下来只要考虑$[l,mid]$中的修改对$[mid+1,r]$中的查询的影响
这时我们发现这其实已经变成了一个静态查询问题,因为所有的查询都发生在修改之后,我们只需要考虑静态查询的问题如何处理即可

介绍就到这里，举出一道例题。

[Violet 3]天使玩偶

Description

.gif)

Input

.gif)

Output

.gif)

Hint

.gif)

题解

DARKBZOJ是个好东西。

这道题我们对于每个询问最好分类讨论。

对于左上角的我们可以把每个询问转换成$(x+y)-(x_p+y_p)_{max}$

并且要求$x_p<x$ , $y_p<y$

其他三部分同理可得。

那么我们把最初的n个点看成n个添加操作，对于这个长度为$(n+m)$的操作序列进行CDQ分治。

显然递归边界就是只有一个的情况，直接返回即可（询问会被之前的修改更新，不用管）。

然后这道题就变得非常简单了啊，用线段树（或者树状数组）维护前缀最大最小值，然后分类讨论坐标即可。

Code明天再写，今天状态实在太差，明天上午最后三节课解决这个问题。