推广一种常数较小，码量不大的 O(n)-O(1) RMQ

critnos · 2021-02-28 09:55:46 · 题解

本文主要参考 https://zhuanlan.zhihu.com/p/79423299

大家都会分块 ST 表吧？

就是把序列分块，每块长度 \log n，对每块的最大值建 ST 表，维护每块的前缀后缀 \max。每次询问的散块可以前后缀 \max，整块可以 ST 表。

但是这样有一个问题，就是当 l,r 落在同一块的时候没有维护。

事实上最广为人知的算法 \pm1 RMQ 为了解决这个问题，通过建立笛卡尔树转化为 lca 问题，然后通过欧拉序求 lca 方法转化为相邻两项相差为 \pm1 的特殊 RMQ。

upd：

感谢上面知乎文章作者 hqztrue 回复，搬运 TA 的一句话（对 \pm1 RMQ 的解释）：

称±1RMQ的两个块本质不同，如果它们相邻作差后形成的±1数列不同(也就是说可以整体平移一个数，e.g. [1,2,3]和[4,5,6]本质相同，因为相邻作差后的数列为[1,1])。本质相同的两个块对于任意询问的答案所在位置都是相同的。

然后块长为 \frac {\log n} 2，则共有 2^{\frac {\log n} 2}=\sqrt n 个本质不同的块，对这些块的每个子段处理，总复杂度 \sqrt n\log ^2 n。再把序列中的每一块映射到对应的本质不同的块上。

但是目测这样常数很大（块长过小导致 ST 表过大，cache miss 严重）。

我们先来回忆一下单调栈（单调递减）的性质：

下标单调递增，下标对应的元素单调递减（废话）

还容易得到，设单调栈（对于整个序列的单调栈）内元素为 p_1\dots p_{size}，序列为 a，序列长度为 n，则 a_{p_1} 为 [1,n] 的最大值，a_{p_2} 为 [p_1+1,n] 的最大值……对于 p_i(1<i\le size)，a_{p_i} 为 [p_{i-1}+1,n] 的最大值。

比如下面的表，显示出了 [1\dots n] 时刻的单调栈。

a:1 3 5 2 4
1:1
2:2
3:3
4:3 4
5:3 5

现在问题来了，如何用上面的单调栈求出 [2,4] 的最大值？

我们找到第 4 时刻的单调栈，第一个 \ge 2 的数 p_i=3，a_{p_i}=5 即为答案。

一般的，对于区间 [l,r]，我们找到 r 时刻的单调栈中第一个 \ge l 的 p_i，a_{p_i} 即为答案。

因为这个数一定在 [l,r] 范围内，且它表示 [p_{i-1}+1,r] 的最大值。因为 p_i 是第一个 \ge l 的数，所以 p_{i-1}<l，p_{i-1}+1\le l，即 [p_{i-1}+1,r] 包含了 [l,r]，故而算法正确。

我们在块内使用这个算法即可。

第一个问题：无法存下所有的单调栈，否则会退化为 \log^2 n 的。

我们采取状态压缩的 trick。一般认为（word-RAM model）计算机字长 w\ge \log n，int 的位数与 w 相同，所以可以把下标在 \log n 规模的单调栈压缩在一个 int 内。换句话说，int 的上界 \ge n。

第二个问题：状态压缩后，如何求第一个 \ge l 的数？

我们使用 l+__builtin_ctz(st[r]>>l)。

解释一下，__builtin_ctz(x) 表示求 x 的二进制表示从末尾开始 0 的个数，st 表示状态压缩的单调栈数组。st[r]>>l 将 [0\dots l-1] 的二进制位去除，只保留 [l\dots r] 的二进制位。设要求出来的数为 v，则末尾应当有 v-l 个 0，加上 l 后正确的求出了 v。

代码实现

以上。