四大离线算法笔记

四大离线算法笔记

四大离线算法

  • 莫队(略)
    • 普通莫队
    • 带修改莫队
    • 回滚莫队
    • 树上莫队
  • 线段树分治(略)
  • CDQ 分治(基于时间的整体二分算法)
  • 整体二分(基于值域的整体二分算法)

CDQ 分治

简单来说,即为对于时间进行分治。

对于某段操作序列 $[l,r]$,分裂成 $[l,mid]$ 和 $[mid+1,r]$,分别执行分治,最后考虑 $[l,mid]$ 中的修改操作对 $[mid+1,r]$ 中的查询操作的影响。

对于每一个 $i$ 号,查询操作,容易证明,在它前面的修改操作都统计到了它的答案里面。

例 1:[Violet] 天使玩偶/SJY摆棋子

很显然,如果暴力计算对于每个询问的贡献的话,枚举在它前面加入集合的坐标,然后计算 $|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
2
3
4
5
6
7
8
9
void solve(ll l,ll r){
if(l==r) return ;
ll mid = (l+r)/2;
solve(l,mid),solve(mid+1,r); //递归
//处理
//清空数据结构
merge(p+l,p+mid+1,p+mid+1,p+r+1,temp+l,cmp); //合并(此处也可以直接排序,特别是左右部分关键字不同的情况)
for(ll i=l;i<=r;i++) p[i]=temp[i];
}

对于普通的 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$ 坐标的大小关系就可以了。

例 3:[HEOI2016/TJOI2016] 序列

设 $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$)

最后转移即可。