线段树分治

Vision271 · 2022-12-15 11:52:09 · 个人记录

概述

• 线段树分治通过将信息下放到时间上的某一段，利用欧拉环游序的特性，高效地离线处理加删问题。

• 简单来说，对于某个元素 x，设其生命周期为 [L,R]（即其在 [L,R] 期间存在），则将其下放到线段树上的对应段。

• 在全部信息离线完毕后，对线段树进行 dfs，利用欧拉环游序或者说入出栈序的特性，确保每个树上标记只被实施一次，撤销一次。

• 而树上标记的数量是 Q\log 级别的，于是有较好的复杂度。

例题

P5787 二分图 /【模板】线段树分治

• 题意：离线加删边，判定是否为二分图。

• 数据范围：n,t\leqslant 10^5,Q\leqslant 2\times 10^5。

• 考虑怎么判定二分图，事实上，二分图、2-SAT、扩展域并查集、最小割建图思想（类似善意的投票那道题）有一些我尚不明了的联系...

• 总之我们还是说一说怎么判二分图。回忆 \text{P1525 [NOIP2010 提高组] 关押罪犯} 这道题的解法：

  • 将每个点拆成两个点，表示位于左部的它和位于右部的它。

  • 两点之间连边代表着两者互相的依赖关系，注意如果 x 左依赖 y 右，那么一定也有 x 右依赖 y 左，反之亦然。

  • 其实这就是个总是是双向边的 2-SAT...好了说回来，我们知道 2-SAT 中一个点的两种状态如果成环则一定无解，那么这里其实就是两个点要并到一个集就无解。

• 于是我们可以高效地用并查集来判断这个 2-SAT 问题的解的存在性。显然我们需要一个可撤销化的，故路径压缩 pass，为了保证复杂度只能按秩合并了。

• 于是得解...注意一点实现细节。O(n\log^2)（认为同阶）。

CF813F Bipartite Checking

• 题意略，相当于板题，不谈了。

CF576E Painting Edges

• 题意略。总之就是半在线版本+卡空间...

• 这里有一个小 trick 就是修改的时候不要动当前所在的位置，因为你已经知道了，于是细节少了好多（不用对首个左区间标记已经做过，也不在所在位置动并查集）。

CF601E A Museum Robbery

• 题意略。问题变成一个背包...

• 还能咋，就暴力背呗，反正复杂度是对的。注意一下空间，虽然线段树只有 O(n) 个点，但是出于优雅的考虑，我们还是手动分配一下吧，毕竟栈里至多只有一条满链。

• 哦，还有一点不同就是这里没法撤销操作。解决办法：在栈里每个点上都存一份状态，往下走的时候新建一个，往回走的时候清掉，嗯...有点类似回滚莫队？

CF938G Shortest Path Queries

• 题意略...trick 大杂烩啊。

• 首先要知道最长/短异或路径的求法，\text{P4151 [WC2011] 最大XOR和路径}，然后要知道可以用并查集来维护异或路径长度，还有最重要的一个：

• 异或边图上的边的等价类。

• 容易看出我们在向下走的过程中要维护一棵异或生成树。其可以是任意的，但真的任意连边的话我们会没法快速求路径。

• 考虑两个生成子树 A,B，记其根分别为 rt_A,rt_B，若现有一条边为 u\in A\leftrightarrow v\in B(w)，则该边等价于 rt_A\leftrightarrow rt_B(w\oplus dis_{A,u}\oplus dis_{B,v})。

• 正确性证明主要是异或的逆运算是它本身，意识到这个结论之后发现在感性上还是很显然的。

• 这就支持我们真的只在生成子树的根之间连边，也即在并查集的族长之间连边；这幅图本身就满足“并查集性”。

• 某种意义上，我们这里的并查集就是变换后的原图...只要在其上维护边长，在回溯到族长的过程中计算距离就可以了。

CF603E Pastoral Oddities

• 题意略。首先，我们必须对这个很不可捉摸的奇度数限制做一步转换：

• 所有连通块都恰有偶数个点。可以证明，这是一个等价变换：

  • 必要性：假设存在至少一个连通块有奇数个点，又所有点的度数为奇数，故总度数为奇数，这是显然不可能的，因为一条边对应两个度。

  • 充分性：对任意恰有偶数个点的连通块，取其任意的一棵生成树。考察根节点以外的每个点，若其有偶数条非树边则连上其余父亲方向的边，否则不然。

  • 发现只有根节点可能有问题，但总度数为偶数，其他点的度数都为奇数，又其他点有奇数个，于是根节点的度数也一定为奇。

• 能快速判定问题就好解决了不少呀~考虑接下来怎么办。注意到答案应当是单调不增的。换言之，每条边生存一段时间然后被更优解代替掉。这很线段树分治。

• 还是先考虑静态做法。最小瓶颈生成树，啊，这里大概算生成合法图？显然还是并查集维护，将边排序后，能合并就合并，因为奇-奇显然合，奇-偶合了更容易把奇变偶，偶-偶乍一看合不合都无所谓，但可能因为奇-偶而在后面变成两个奇，所以还是得连。

• 但是这里...这里我们要往里面插入边。显然这是不可做的...但总不能每加一条就重来啊。

• 倒序，时光倒流！我不是很好描述这个...总之，我们首先将所有边按边权从小到大排序，然后暴力跑一遍；不妨记结果为 res，则所有边权 \leqslant res 的边都是“不更劣的”。

• 换言之，当我们从有 m 条边倒退到有 m-1 条边时，由上面的结论，答案单调不降；换言之，\leqslant res 的边都是可用的。

• 既然如此，就把它们 rev 到出现时间到当前时间 -1 这一段上；在走的时候强制把这些边“用掉”，即不必须连但可以使用它们做贡献。

• 到了叶节点之后，可以证明，我们 Kruskal 的指针一定不更靠左，于是向右暴力扫就好。

• 复杂度的话，Kruskal 这部分是 O(m\log)，因为每条边至多被扫到一次；线段树分治当然是 O(m\log^2) 的，因为每条边被拆成了 \log 条。

• 另外，也可以整体二分。主要的问题在于初始化并查集的复杂度太高以及向右子树走的话状态不好继承，于是考虑改 bfs 序在同层从左扫到右。O(m\log^2)，一只是整体二分，一只是并查集。

• 虽然乍一看 dfs 只维护一条链上的并查集然后右继承左也行，但仔细思考会发现每次向左走都要复制一份并查集，初始化复杂度还是没法接受。

• 反而是直接暴力撤销的 dfs 是对的，因为对于每个区间，其左半边的边会被加-删-加，和只加一遍只有常数差异，根据整体二分的性质，这等效于每条边被加 \log 遍。