do_while_true's blog

晚风中闪过 几帧从前啊

0%

「学习笔记」分块和莫队

各类根号算法。不太适合当作复习所用,就当写个教程了,可能因为这个东西不大需要复习(

关于复杂度分析:在实践中还是不要套式子,应当直接分析。

关于块长:在实践中还是不要套式子,应当直接调块长看怎样跑得快。

分块

有时候不同操作的数量不同,比方说一般的普通莫队,会有 $\mathcal{O}(n\sqrt n)$ 次修改,但是只有 $\mathcal{O}(n)$ 次查询,这个时候若采用 $\mathcal{O}(1)$ 修改,$\mathcal{O}(\sqrt n)$ 查询,就会得到 $\mathcal{O}(n\sqrt n)$ 的优秀复杂度!

常用来复杂度平衡的分块:

$\mathcal{O}(\sqrt n)$ 区间修改 $\mathcal{O}(1)$ 单点查询

序列分块,整块打标记,散块暴力修改。

$\mathcal{O}(1)$ 单点修改,$\mathcal{O}(\sqrt n)$ 区间求和

序列分块,维护整块总和,散块暴力查。

$\mathcal{O}(\sqrt n)$ 区间加,$\mathcal{O}(1)$ 区间求和

对于每个块维护块内前缀/后缀和,维护整块之间的前缀和。

修改:对于块内前缀后缀和:整块打标记,散块暴力重构;整块之间的前缀和暴力修改。

查询:整块为两个前缀和相减,散块查这个块里面的前缀后缀和。

$\mathcal{O}(1)$ 区间加,$\mathcal{O}(\sqrt n)$ 区间求和

类似上一个,对于每个块维护块内差分,维护整块之间的差分。

更好写的做法:差分一下,$\mathcal{O}(1)$ 单点修改,区间求和变成两个前缀求和,那么就只需要求 $\mathcal{O}(\sqrt n)$ 求前缀 $(x+1-i)\times a_i$ 的值,维护 $\sum a_i$ 和 $\sum a_i\times i$ 即可。

$\mathcal{O}(1)$ 添加一个数,$\mathcal{O}(\sqrt n)$ 查询第 $k$ 大

值域分块,维护整块里有多少个数,询问的时候直接从小到大遍历整块直到不够的时候再查散块。

$\mathcal{O}(\sqrt n)$ 添加一个数,$\mathcal{O}(1)$ 查询第 $k$ 大

对排名这一维分块,然后对于每个块用 deque 维护一个排序序列。插入的时候找到这个数所在的 deque 暴力插,后面的 deque 是若干个 push_front 和 pop_back。

查询的话直接定位该排名到所在的块,查询 deque 里第 $k$ 个值就可以了(deque 的定位是 $\mathcal{O}(1)$ 的)。

莫队

我的理解:莫队是在高维上利用分块的一种扫描线。或者说,在高维上的若干点的最小生成树上 dfs。

理想莫队信息:维护一个子集的信息,支持 $\mathcal{O}(a)$ 插入一个元素,$\mathcal{O}(b)$ 删除一个元素,无法比直接暴力插入更高效地合并。

普通莫队

设块长为 $B$,易分析得出端点移动次数为 $\frac{n^2}{B}+mB$,若 $n,m$ 同阶,取 $B=\sqrt n$ 最优。但实际上,根据数据生成的方式不同,不同的块长在效率上也有所不同,但我们这里暂且讨论复杂度上问题,不考虑数据不同带来的影响。

莫队掌握的经典技巧是复杂度平衡。

如果 $m<n$,取块长 $\frac{n}{\sqrt m}$,移动次数和查询次数得到平衡,左右端点移动次数和查询次数均为 $\mathcal{O}(n\sqrt m)$,这一步是根据均值不等式来得出的。

举个栗子,例如每次端点移动是区间修改,查询是单点查询,$n,m$ 同阶。这个时候如果用线段树或者树状数组,复杂度为 $\mathcal{O}(n\sqrt n\log n)$.但是注意到询问只有 $m$ 次,询问的复杂度比修改的复杂度还要低,尝试平衡修改和询问的复杂度,采用序列分块来做到 $\mathcal{O}(1)$ 修改 $\sqrt n$ 查询,这样总复杂度就是 $\mathcal{O}(n\sqrt n)$.

还有诸如把 $\log$ 放进根号里面的技巧,当然这都是理论上的东西,在实践中,由于实现不同部分的常数差异,块长有时候取得更大或者更小是更优的。

下面整理的几种莫队我认为都是更偏向于 trick 或者套路而并非模板。

带修莫队 & 高维莫队

啊这个玩意是不是在时间上多了一维的莫队!

如果有修改,那么就加上一维时间,这里令 $n,m$ 同阶,故分析时所有 $m$ 均由 $n$ 替代。

按照 $B$ 为块长分块,共有 $\frac{n}{B}$ 个块。排序的时候先按照左端点所在块排序,再按照右端点所在块排序,再按照时间排序。然后三个指针去扫。

  • 左右指针所在块编号不变时,块之内的时间指针移动次数是 $\mathcal{O}(n)$,块之间的时间指针移动次数也是 $\mathcal{O}(n)$;左右指针所在块编号的种数是 $\mathcal{O}((\frac{n}{B})^2)$,所以时间指针移动总复杂度是 $\mathcal{O}(\frac{n^2}{B})$.
  • 左指针所在块编号不变时,对于相邻两个询问,右指针在块之内移动次数是 $\mathcal{O}(B)$,在块之间移动次数是 $\mathcal{O}(B)$;左指针所在块编号改变时,右指针移动 $\mathcal{O}(n)$,左指针所在块编号改变 $\mathcal{O}(\frac{n}{B})$ 次。所以右指针移动的总复杂度为 $\mathcal{O}(nB+\frac{n^2}{B})$.

  • 左指针移动次数易分析得 $\mathcal{O}(nB)$.

所以总时间复杂度为 $\mathcal{O}(nB+\frac{n^2}{B})$,根据均值不等式,取 $nB=\frac{n^2}{B}$ 时,即 $B=n^{\frac{2}{3}}$ 最优,总时间复杂度为 $\mathcal{O}(n^{\frac{5}{3}})$.

一般化:高维莫队

$★$ 方法:对前 $k-1$ 维分块,按照第 $i$ 关键字为第 $i$ 个维度的所在块编号排序,第 $k$ 维关键字为第 $k$ 维坐标。

尝试用扫描线的角度来一般化在 $k$ 个维度上做莫队的过程,这里假设指针的移动是 $\mathcal{O}(1)$ 的,每一处指针移动次数都要和 $m$ 取 $\min$.

考虑第 $k$ 维指针的总移动次数:块数乘上 $n$ 也就是 $\mathcal{O}(\frac{n^{k}}{B^{k-1}})$;

对于第 $i$ 维,考虑前 $i-1$ 维在同一个块内,第 $i$ 维指针的移动次数:它每次移动 $\mathcal{O}(B)$ 次,一共移动 $\mathcal{O}(mB)$ 次。

对于第 $i$ 维,考虑前 $i-1$ 维在不同块之间第 $i$ 维指针的移动次数:

  • 从一个块到下一个相邻的块,每次移动 $\mathcal{O}(B)$ 次,一共移动 $\mathcal{O}(mB)$ 次;

  • 从最后一个块到第一个块,每次移动 $\mathcal{O}(n)$ 次,仅会在前面维度的块改变的时候才会移动,前面维度的块数为 $\mathcal{O}(\frac{n^{i-1}}{B^{i-1}})$,所以这部分移动次数是 $\mathcal{O}(\frac{n^i}{B^{i-1}})$,向上松一松就是 $\mathcal{O}(k\frac{n^k}{B^{k-1}})$,由于通常 $k$ 不是很大,那就视这个 $k$ 为常数。

综上所述,指针移动次数为 $\mathcal{O}(\frac{n^{k}}{B^{k-1}}+mB)$,同样根据均值不等式得到 $B=\frac{n}{m^{\frac{1}{k}}}$ 时最优,时间复杂度为 $\mathcal{}(nm^{\frac{k-1}{k}})$

树上莫队

查询的信息:

  • 链信息
  • 子树信息

其中如果查询的子树信息是理想莫队信息,那么直接启发式合并即可。

链上查询信息的方法:

  • 信息可以差分,一条链差分成四个点到根的路径(四维降成二维)
  • 对于连通块进行分块(树分块)
  • 对于括号序分块

理想莫队信息,第一种方法就不行了,第三种方法相比于第二种代码难度和常数都更优。

那么解决思路大概就是,把树的信息用括号序变成序列,然后在上面跑莫队。

括号序

假设点 $x$ 的入栈时间为 $in_x$,出栈时间为 $out_x$.

对于括号序上的一段区间,如果它仅出现一次,那么就统计上它的信息。

假设现在要询问树上路径 $u\to v$ 的信息。如果它们互为祖先关系,假设 $u$ 是 $v$ 的祖先,那么这条路径的信息就相当于括号序 $[in_u,in_v]$ 的信息。

如果它们不互为祖先关系,假设 $out_u<in_v$,那么这条路径的信息就相当于 $[out_u,in_v]$ 的信息。

括号序还可以用来判断两点间是否存在祖先关系,判断 $u$ 是否是 $v$ 的祖先等价于判断 $[in_u,out_u]$ 是否完全包含 $[in_v,out_v]$.

这样在括号序上跑莫队就可以维护信息了。

回滚莫队

在正常的问题中,普通莫队是不断移动左右端点来维护答案。但有的问题,插入和删除复杂度是不一样的。有时候插入更快一些,有时候删除更快一些。采用只插入不删除,或者只删除不插入的莫队,称之为回滚莫队。

仍是按照左端点所在的块为第一关键字,按照右端点为第二关键字排序。

$★$ 只插入莫队:初始左端点为所在块右端点,右端点从小往大扫,每次处理询问的时候直接撤销左端点的影响,重新从块的右端点开始移动。

$★$ 只删除莫队:类似地,初始左端点为所在块左端点,右端点从大往小扫,每次处理询问的时候直接撤销左端点的影响,重新从块的左端点开始移动。

很多博客都是让左右端点在同一块内的暴力扫,对于只删除莫队,如果散块询问不好暴力扫得出,一并加入到最后扫莫队也是不影响的。

二次离线莫队

咋一看上去很高深,其实并不难,其实也是一种思想?

例题:多次询问区间逆序对,允许离线(洛谷 P5047)

很容易想到一个 莫队+树状数组 的做法。每次移动指针的时候用树状数组来计算答案的变化。一共有 $\mathcal{O}(n\sqrt m)$ 次单点修改,区间查询。

注意到这个过程本质上还是在做数点,那把区间查询差分成前缀查询,然后把这些询问离线下来,做数点。这样就只有 $\mathcal{O}(n)$ 次单点修改,$\mathcal{O}(n\sqrt m)$ 次区间查询,用 $\mathcal{O}(\sqrt n)$ 单点修改,$\mathcal{O}(1)$ 区间查询,就可以做到 $\mathcal{O}(n(\sqrt n+\sqrt m))$ 的时间复杂度。

但是卡空间,而空间复杂度为 $\mathcal{O}(n\sqrt m)$,优化空间的话,假设是右端点向右移动(其余移动情况同理),每次都是询问 $([1,r-1],r)$ 产生的逆序对,而这个可以预处理出来之后作前缀和来 $\mathcal{O}(1)$ 得到;还有询问 $([1,l-1],r)$ 的逆序对,注意到 $l-1$ 是固定的,那么把 $[r,qr]$ 两个区间端点挂在 $l-1$ 处即可。这样空间就是线性的了。

小结

前面提到莫队本质上是离线下来作扫描线,而把莫队指针移动的的过程中所做的修改和询问操作,再离线下来,通过扫描线等技巧优化复杂度处理,就是二次离线了!

根号重构

本节整理自 lxl 的课件。

本质上是对时间分块。

基于这么一个套路:

  • $\mathcal{O}(x)$ 重构整个序列;
  • $\mathcal{O}(y)$ 计算一个修改操作对一次查询的影响;
  • 每隔 $t$ 个修改重构整个序列。

对于查询,其总复杂度为 $\mathcal{O}(mty)$;对于重构,其总复杂度为 $\mathcal{O}(\frac{mx}{t})$.

经典问题

维护一棵树,支持断边,加边,链 kth。

考虑根号重构,每 $\sqrt m$ 重构一次。

这样询问就转化成查询 $\sqrt m$ 段树链总的 kth。

用可持久化线段树维护,每次询问在这 $\sqrt m$ 个可持久化线段树上一块儿二分。

查询复杂度 $\mathcal{O}(\sqrt m\log n)$,重构复杂度 $\mathcal{O}(n\log n)$,总复杂度 $\mathcal{O}((n+m)\sqrt m\log n)$.

小结

lxl 的话:

在复杂的范围修改查询问题中,可以考虑根号重构。

这里是一个统计规律。

实际上我认为是对于复杂的范围修改查询问题,维之间是不对称的,时间维是结构最简单的,对其进行分块容易出好的效果。

我暂且还没有那么深的理解,没有深刻理解到“维之间不对称”,对于“时间维结构较简单”稍微有那么一点感觉(?),还需要多做点题。

我对后半句理解大概就是,时间维的结构是简单的,因此尝试在时间维上维护信息。类比序列上的线段树和树状数组,在时间维上维护信息的方法有线段树分治和根号重构。

Trick 和例题

$\sum a_i\leq n$,不同的 $a_i$ 只有 $\mathcal{O}(\sqrt n)$ 种。

先咕着