本文收录部分 $\Theta(n)$ 预处理 $\Theta(1)$（$\Theta(n)-\Theta(1)$）操作的强制在线算法（这个说法准确吗……反正大概就这意思啦）。

对于同一个问题可能不会收录所有算法，点名 RMQ。

基本前置：Word-RAM Model（$w=\Omega(\log n)$）。

1.RMQ

世界名画。

首先我们很容易导出一个 $\Theta(n\log n)-\Theta(1)$ 的算法，用 ST 表还是二区间合并看心情。我们把原序列按 $\Theta(\log n)$ 分块，块间运行这个算法。

询问如果跨块则可以用一个后缀+块间+一个前缀拼起来，其中前后缀显然也可以 $\Theta(n)$ 预处理出来。当然如果不在意常数的话，前后缀的部分也可以一并用块内的算法运行，无妨（事实上这样比较方便在板子题测正确性）。

那么我们现在仅考虑一个块内的询问。我们考虑 RMQ 的一种 $\Theta(n)-\Theta(\log n)$ 离线算法：把询问 $[l,r]$ 按右端点排序，扫描线维护序列 $[1,r]$ 下标上的单调栈。我们发现单调栈的一个位置 $i$ 实际上代表着 $[i,r]$ 的后缀最小值在 $i$，那么我们在单调栈上二分找到第一个 $\ge l$ 的位置就可以了。我们试图把这个算法套上块。由于序列长度仅为 $O(\log n)$，我们实际上可以把每个位置的前缀单调栈压在一个二进制数里，进而把每个位置的前缀单调栈都存下来。这一步让我们不再需要离线。至于找第一个 $\ge l$ 的位置更是可以用一步位运算直接化归到找一个二进制数最低位 1 的位置，而这个是可以 $\Theta(1)$ 做的。这一步让我们撇去了复杂度里的 $\log$。

综上所述，我们现在的 RMQ 算法成功被优化成了 $\Theta(n)-\Theta(1)$。

2.LCA

常数比较好的写法是 dfs 序求 LCA，序列长度上比欧拉序求 LCA 短一倍。在此介绍一下。

考虑我们现在求 $u$ 和 $v$ 的 LCA，不妨有 $dfn_u\le dfn_v$，这里 $dfn$ 指节点的 dfs 序。

如果 $u=v$ 那么答案就是 $u$，直接判掉；否则，我们考虑 $[dfn_u+1,dfn_v]$ 这一段 dfn 上对应深度最小的节点。如果 $u$ 是 $v$ 的祖先，那么这个点一定是 $u$ 的儿子；否则，考虑从 $u$ 到 $v$ 的 dfs 过程中一定不会再经过 LCA（其在 $u$ 前已被访问），也不会跨越到 LCA 的子树之外。考虑到 $u$ 与 $v$ 在 LCA 的不同子树中，这部分一定会访问到 $v$ 对应子树的根（否则无法跨越到该子树内），那么这个根就是我们求出深度最小的节点。我们发现，这个节点一定是 LCA 的儿子，直接取它的父亲作为答案即可。

求区间最小深度这部分使用 RMQ 的优化，我们把 LCA 也成功优化成了 $\Theta(n)-\Theta(1)$。

3.LA

其实就是给定一棵树求给定点的给定级祖先。根据长链剖分那一套理论我们有一个简单的 $O(n\log n)-\Theta(1)$ 算法。我们简单优化一下这个东西并把它改成 $O(p\log n)-\Theta(1)$ 的，其中 $p$ 是树的叶子数。考虑到我们唯一更改的其实是只需要维护每个叶子的二的幂级祖先，这个我们在 dfs 的过程中维护一个祖先栈并在访问到叶子时直接根据下标找祖先即可。

这里我们介绍一个有趣的东西：ART Decomposition。简单来说，这个算法对树进行分解。考虑每个极高（自身满足且父亲不满足或没有父亲）点满足其子树有 $O(B)$ 个节点，那么很显然所有这些被取出的子树两两无交。把所有这些子树从原树上删去，那么新树的叶子必然满足原来子树内有 $\Omega(B)$ 个点，那么新树有 $O(\frac nB)$ 个叶子。我们取 $B=\Theta(\log n)$，那么新树可以直接跑那个长剖算法，我们把问题规模实际上降低到了 $O(\log n)$。

（注意这里 ART 玩起来很舒适是因为我们的复杂度瓶颈给到了叶子数量上。如果不是这样的话，我们还需要考虑把只有一个儿子的节点和儿子压起来，并用一个链上数据结构处理压起来的链。一般而言为了复杂度考虑这部分还得再分块，而且有时需要不同的维护方法，主打的就是一个阴间。）

我们套娃一层，现在问题的规模变成了 $O(\log\log n)$。那么我们对于每个点存下它的所有祖先，这需要的二进制位数是 $O(\log\log n\log\log\log n)$ ，也即 $O(w)$ 的。接下来根据一些简单的位运算操作我们就可以在常数时间内求出 k 级祖先了。

upd on 2024.10.16：上面那个写的时候脑子不好，实际上括号序的种类数十分有限，即使带上 LA 的两个参数实际情况数也很少，可以直接预处理，不用叠层了。

我们把 LA 也成功优化成了 $\Theta(n)-\Theta(1)$。

4.UFDS（上树版）

我们现在解决这样一个问题：给定一棵树支持两种操作：连接一个点与父亲的边，或者查询两个点是否联通。

老规矩，我们先试图导出一个 $O(n\log n)-\Theta(1)$ 的算法。考虑对每个点维护其联通块编号，合并时启发式合并即可。简便起见，我们的启发式合并可以直接用度数之和，这样在树上就可以直接暴搜求 size 了。

我们考虑把树按 $\Theta(\log n)$ 分块。块间显然可以运行这个算法。至于块内，我们考虑把一个点与父亲的断边状态用一个布尔值标记作为这个点的点权。我们考虑用一个联通块内最高的点作为这个联通块的根，那么一个点所在联通块的根就是最低的权为 1 的点。我们考虑把每个点按照拓扑序（具体的爱啥序啥序）排列并顺次对应给一个二进制位，这一位的值表示这个点的权值；然后我们对于每个点维护一个二进制数压缩存储块内的每一个数（拓扑序位置意义下）是否为其祖先。查询的时候把两个部分按位与然后取最高位（拓扑序最大）即可。

我们还涉及到另外一个问题：查 $u$ 和 $v$ 所在块的 LCA，以及其块与两段路径对应的临界点。我们考虑 LCA 那个算法，求出最小值所在位置附带本身 dfs 序作为第二关键字，那么求出最大 dfs 序的最小值就是 $v$ 所在块一边路径与 LCA 的临界点。至于 $u$ 的临界点，可以直接暴力反过来搞一遍，也可以求出最小 dfs 序的最小值再维护一下其左边的兄弟，没有所谓。我们把 UFDS 也成功优化成了 $\Theta(n)-\Theta(1)$。

5.SDFU（？）

标题瞎起的，本质上就是想说把 UFDS 的问题反过来：给定一棵树支持两种操作：断开一个点与父亲的边，或者查询两个点是否联通。别忘了这篇文章的大前提是强制在线。

我们发现块内并没有什么区别，我们接下来只考虑怎么导出一个 $O(n\log n)-\Theta(1)$ 的算法。我们注意到上面那个启发式合并的算法，如果我们每次能精准找到断开两部分中 size 较小的一个并重新赋联通块编号，那么我们的问题就解决了。我们考虑修改一下 dfs 的步骤：维护一个栈，每个元素有三个部分：当前点，当前点的前驱和已经搜到了这个点的哪一条出边；每一次，弹出栈顶元素，把对应出边的点（若合法）入栈，然后修改原栈顶的已搜到出边。如此一来，我们考虑直接对断开边 $(u,v)$ 的 $u$ 和 $v$ 进行一个平行的 dfs，哪边先到底哪边就 size 较小。当我们找到较小的 size 时另一边也至多搜了这个规模次，于是我们的复杂度就正确了。继续树分块，我们把 SDFU（？）也成功优化成了 $\Theta(n)-\Theta(1)$。

6.区间绝对众数

标题终于不是令人迷惑的字母缩写力（喜）。

注意这个做法依赖哈希，所以不同于其他命题，这个东西的复杂度会看起来有点蠢。不过哈希一般是可以防卡的，所以先这样吧。

我们把问题分为两部分：求值和检验。

对于求值，老规矩 $\Theta(\log n)$分块，由于摩投具有结合律所以块间可以直接猫。块内递归一层把问题规模降到 $O(\log\log n)$，注意到这时候离散化后的本质不同序列和查询只有 $O((\log\log n)^{\log\log n}\times(\log\log n)^2)=O(2^{\log\log\log n\times\log\log n}(\log\log n)^2)$ 也即 $O(n)$ 种。直接摩投预处理即可。

对于检验，就是给定 $[l,r,x]$ 判断 $x$ 是否为 $[l,r]$ 的绝对众数。我们有结论，对于给定的 $x$，其作为绝对众数出现的所有区间并集大小和是 $O(c)$ 的，其中 $c$ 为 $x$ 的出现次数。具体证明可以考虑把折线图画出来然后对于每个峰把贡献累进去然后缩掉。我们考虑如何求出这个并集。我们考虑枚举“一段并集中的极长连续段左起第一个 $x$”出现的位置 $k$，可以证明其一定是 $2i-p_i$（$p_i$ 表示 $x$ 第 $i$ 次出现的位置）某个前缀最小值所在处（的 $p$）。我们注意到这个连续段的左端点一定存在一个可以实现绝对众数的区间满足其右起第一个 $x$ 出现的位置是 $k$ 开始第一个后缀最大值，而右端点对应区间右起第一个 $x$ 出现的位置是能承受的极远后缀最大值，这两部分都可以双指针维护，最后把所有区间丢一起取并（左端点天然单调）然后用一个游标维护所有并集中的极长连续段（及其左端点前一个位置）的 $x$ 出现次数的前缀和，用哈希表维护。我们意识到，如果前缀和表中查不到 $l-1$ 或者 $r$ 那么一定寄了，否则我们两个前缀和一减就可以判了。

如此一来，我们把区间绝对众数也优化成了 $\Theta(n)-\Theta(1)$，虽然是期望意义下的。

7.RMSQ

人话：区间最大子段和。

我们不妨原序列是 $A$，下标从一开始。我们首先计算其前缀和数组 $C$，规定 $C_0=0$。我们考虑对于 $C$ 的每一个位置 $i$ 求出其之前最后一个 $C$ 值不小于自己的位置 $L_i$，若不存在则记为 0。我们于是有了第一条性质：$\forall i\in[1,n],j\in(L_i,i)$ 有 $C_j\lt C_i$。我们注意到，对于子段 $[j,i]$，如果 $j\le L_i$，那么换成 $[j,L_i]$ 一定不劣，于是我们不需要考虑这样的子段对答案的可能贡献。

我们再对于每个 $i$ 预处理 $[L_i,i)$ 上 $C$ 的最小值位置加一（如果有多个，取最靠右的那一个），记作 $P_i$。我们于是有了第二条性质：$\forall i\in[1,n],j\in[P_i,i)$ 有 $C_j\gt C_{P_i-1}$。综合这两条性质我们可以推出：$\forall i\in[1,n],j\in[P_i,i)$ 有 $C_j\in(C_{P_i-1},C_i)$。

（当然 $P$ 的定义本身也带给我们一个比较显然的性质：$\forall i\in[1,n],j\in[L_i,i)$ 有 $C_j\ge C_{P_i-1}$。这个不用太过在意。）

我们再记 $M_i=C_i-C_{P_i-1}$，换而言之就是 $[P_i,i]$ 的区间和。我们注意到，对于以 $i$ 为结尾的有效子段 $[j,i]$，由于 $j\in(L_i,i]$，故其和 $C_i-C_{j-1}\le C_i-C_{P_i-1}$。也就是说，如果只是要求全局的最大子段和，我们把所有 $M$ 取 $\max$ 已经做完了。

考虑对 $[l,r]$ 区间查询的解决方案。我们考虑暂且无视 $P$ 的限制直接硬做，求出 $M_l$ 到 $M_r$ 的最大值所在位置 $i$。如果 $P_i\ge l$，那我们显然已经做完了，返回即可。否则我们即有 $P_i\lt l$。由于 $P_i\gt L_i$，我们得到 $L_i\lt l$。根据我们前面的性质，我们推得 $\forall j\in[l,i)$ 有 $C_j\lt C_i$，也就是说以 $j$ 为结尾的最大子段和一定不如改成以 $i$ 结尾，直接不考虑。对于以 $i$ 为结尾的最大子段，其左端点减一的 $C$ 值要取到最小，这是一个 RMQ 的形式，直接做掉即可。对于以 $j\in(i,r]$ 的最大子段，我们考虑 $P_j$ 的位置：

若 $P_j\le P_i$：$P_i\in[L_j,j)$，推出 $C_{P_i-1}\ge C_{P_j-1}$；$i\in(L_j,j)$，推出 $C_i\lt C_j$。进而 $M_j=C_j-C_{P_j-1}\gt C_i-C_{P_i-1}=M_i$，与 $M_i$ 的最大性矛盾。

若 $P_i\lt P_j\le i$：$i\in[P_j,j)$，推出 $C_i\gt C_{P_j-1}$；但 $P_j-1\in[P_i,i)$，推出 $C_{P_j-1}\lt C_i$，矛盾。

若 $i\lt P_j\le j$：$P_j\ge l$，这是一个合法的区间。

综上所述，对于 $j\in(i,r]$，一定有 $P_j\ge l$ 合法，直接在 $M$ 上查 RMQ 即可。

于是我们就在三次 RMQ 内解决了区间最大子段和问题。由于 RMQ 已经是 $\Theta(n)-\Theta(1)$ 的了，我们把区间最大子段和也优化成了 $\Theta(n)-\Theta(1)$。

总结一下，序列上的问题化归到最后本质上基本都是 $\log$ 分块然后块间二进制瞎搞（个别的递归一层）。树上的问题除了 LCA 拍上链以外别的基本都是用的树分块或者 ART（实际上 UFDS 和反问题也可以这么搞，就是有点阴间）。

更多的问题能不能用类似的套路搞，比如区间 or？或者进一步区间 nand？限于笔者水平，在此不得而知，若读者有所了解，还请不吝赐教；如若文章存在纰漏，也请劳烦指出。

有个暴论，一个正常的 01 序列静态区间查询全都可以这么搞，因为 $\log$ 分块后块内总状态数有限，如果不行就再递归一层。

至此，且容我暂且搁笔。