四大离线算法笔记
四大离线算法
- 莫队(略)
- 普通莫队
- 带修改莫队
- 回滚莫队
- 树上莫队
- 线段树分治(略)
- CDQ 分治(基于时间的整体二分算法)
- 整体二分(基于值域的整体二分算法)
CDQ 分治
简单来说,即为对于时间进行分治。
对于某段操作序列 $[l,r]$,分裂成 $[l,mid]$ 和 $[mid+1,r]$,分别执行分治,最后考虑 $[l,mid]$ 中的修改操作对 $[mid+1,r]$ 中的查询操作的影响。
对于每一个 $i$ 号,查询操作,容易证明,在它前面的修改操作都统计到了它的答案里面。
很显然,如果暴力计算对于每个询问的贡献的话,枚举在它前面加入集合的坐标,然后计算 $|x_1-x_2|+|y_1-y_2|$ 的最小值就行了,注意到最小值是可以合并起来计算的,即不会相互影响,那么我们就可以用 CDQ 分治优化。
对于每个区间 $[l,r]$,先分裂,再递归,最后合并。
主要处理合并的问题,左边的修改可以对右边造成影响,且为了保证时间复杂度,这里的查询必须是 $O(\log)$ 级别的,这样的话整体时间复杂度才能是 $O(\log^2)$ 级别。
很显然,两边分别按 $x$ 排序,然后假设当前算某个询问点左下角距离它最近的点的答案,那么要求 $x_{add} \le x_{que}$ 且 $y_{add} \le y_{que}$。
然后用树状数组维护 $y$ 轴就可以了。
一共跑 $4$ 遍,但是写得好的话可以减少很多时间复杂度。
1 | void solve(ll l,ll r){ |
对于普通的 CDQ 分治,核心代码就这样。
例 2:
给定 $n$ 个三维空间中的点,对于每个点 $i$,找到 $j$ 使得 $x_j <x_i,y_j < y_i,z_j<z_i$ 的数量。($1 \le n \le 10^5,1 \le x_i,y_i,z_i \le 10^9$)
还是像上面的问题一样,将每个点看做一次询问加一次修改,注意到如果我们按点的 $x$ 轴大小顺序去加点的话是不会对答案产生影响的,因此我们先按 $x$ 从小到大排序,然后用 CDQ 分治处理 $[l,mid]$ 对 $[mid+1,r]$ 的答案。
很容易发现所有位于 $[l,mid]$ 的点的 $x$ 总是小于等于 $[mid+1,r]$ 的点,那么我们仍然按 $y$ 坐标合并上来,然后双指针维护 $z$ 坐标的大小关系就可以了。
设 $b_i$ 表示 $a_i$ 的最小可能值,$c_i$ 表示 $a_i$ 的最大可能值,那么 $i,j$ 可以连接起来当且仅当 $i<j,c_i \le a_j,a_i \le b_j$。
这又是一个类似于上面问题的“偏序”问题,那么还是像上面一样处理答案,不过这次我们要先递归 $[l,mid]$,然后处理 $[l,mid]$ 对于 $[mid+1,r]$ 的贡献,最后递归 $[mid+1,r]$。
原因是因为 DP 的顺序是从小到大的,因此 CDQ 的顺序也得从小到大来计算,当然统计方案一般不存在这种问题,所以两种写法都是可以的。
总结一下:
- CDQ 用于处理左边的贡献可以合并且仅对于右边的询问产生影响的问题。
- CDQ 也用于求解一些偏序问题。
- CDQ 实际上是遍历一棵线段树,前序、中序和后序三种遍历方式需要视问题的不同而处理。
(CDQ 分治也可以用来动态维护凸包,即优化斜率优化 DP,当然这种情况一般能被李超线段树代替,时间空间均差不了多少)
整体二分
简单来说,即为对值域进行分治求解。
假设我们知道了某些的询问的答案在 $[l,r]$ 内,而且可以通过 $O(\log)$ 的判定每个询问的答案在 $[l,mid]$ 还是在 $[mid+1,r]$ 内,那么可以在 $O(n \log^2 n)$ 的时间复杂度内求解每个询问。
一些条件:
- 询问具有可二分性。
- 询问次数和数据的大小级别相当。
时间复杂度:每个询问最多被遍历 $\log$ 次,每次需要 $O(\log)$ 的时间判定,即 $O(\log^2)$ 级别。
例 1:
查询某个区间第 $k$ 小的数,没有修改,要求 $O(n \log^2 n)$ 内的时间,空间 $O(n)$。
很明显每个询问具有可二分性,那么我们可以整体二分。
假设答案小于等于 $mid$,那么把 $a$ 序列中的所有小于等于 $mid$ 且大于等于 $l$ 的数都设为 $1$,那么如果询问区间内的 $1$ 的个数大于等于 $k$,那么这个询问的答案就在 $[l,mid]$ 内,否则在 $[mid+1,r]$ 内。
注意:如果这个询问被划到了 $[mid+1,r]$ 区间,那么 $k$ 要减去当前区间 $1$ 的个数,即去掉 $[1,mid]$ 内的数。
例 2:[CTSC2018] 混合果汁
判定就很简单了,用线段树上二分即可,此处不啰嗦。
类似于 CDQ 分治的第三道题目,我们在整体二分的时候需要先判定,然后处理在 $[l,mid]$ 里面的询问,然后清空,最后再处理 $[mid+1,r]$ 里面的询问。
至于为什么要这么做,因为每次判定必须用到 $[mid+1,n]$ 里面的信息,而我们不可能每次判定都循环 $mid+1 \sim n$,只能从前面的判定获取有用信息,$k$ 小值也可以用这种方法。
这样的话时间复杂度依然是 $O(n \log^2 n)$。
例 3:Yet Another Minimization Problem
四边形不等式:
$$
w(a,c)+w(b,d) \le w(a,d)+w(b,c)
$$
我们可以简记为:交叉小于包含。
如果对于某个 dp 转移形如这种形式:
$$
f_r = \max{f_l+\operatorname{value}(l,r)}
$$
如果 $\operatorname{value}$ 满足四边形不等式,那么 $f$ 函数满足决策单调性。
这里讲解 $f$ 函数是分阶段得到的,才能满足可用整体二分求解,否则需要用单调队列,后面再说。
整体二分求解很简单,$\operatorname{solve}(l,r,s,t)$ 表示 $f_l \sim f_r$ 的决策点一定位于 $s \sim t$ 中,然后每次找到 $mid = \dfrac{l+r}{2}$ 的决策点进行递归,层数一共有 $n$ 层,每层遍历 $s \sim t$,故时间复杂度为 $n \log n$。
注意,每层仅可遍历 $l \sim r$ 和 $s \sim t$,不可遍历其它内容,除非时间复杂度确定,不然的话无法保证 $\log$ 级别的消耗。(类似于遍历 $l \sim t$)
最后转移即可。