浅谈 O(n)-O(1) rmq

说到 $O(n)-O(1)$ rmq 问题，最广为认知的就是四毛子，但是四毛子不好写，因此来记录几个较为好写的 $O(n)-O(1)$ rmq 算法。

分块

• 优点：较为好写，且能够做到严格的 $O(n)-O(1)$。
• 缺点：不能算非常好写。

将序列按照每 $\log n$ 个元素分为一块，序列将被分为 $\frac{n}{\log n}$ 块，求出每个块内的最大值，并在块间建立 ST 表。并且对于每个块内，处理出前缀和后缀最大值。

对于一个询问 $[l,r]$，找出被完全包含的区间，求出这几个块之间的最大值，对于两边的散块，调用前后缀最大值即可。

至此，预处理时间复杂度 $O(\frac{n}{\log n}\cdot \log n+n)=O(n)$，查询时间复杂度 $O(1)$。

看似结束了，但是如果询问的区间被包含在了一个块内该怎么办呢？

在预处理时，可以对于每个块内分别跑一遍单调栈，维护块内每个位置的前缀的后缀最大值。同时，单调栈内的元素个数是 $O(\log n)$ 的，每个元素可以用他在块内的位置表示，值域也是 $O(\log n)$ 的。

我们可以将者 $O(\log n)$ 个值域为 $O(\log n)$ 的数压缩成一个值域为 $O(\log^{\log n} n)$ 的 long long 记录下来，不难发现这个 long long 可以在入栈和弹栈的时候同时维护。

另一种存贮方式是对于每个数，记录这个数到当前块的开头哪些位置在单调栈中，每次询问是可以使用 __builtin_ctz 函数进行查询。这种方式所使用的空间更少，单个元素的值域是 $O(2^{\log n})=O(n)$。

询问时，直接调用 $r$ 所在位置的单调栈信息即可，不难发现复杂度也是 $O(n)-O(1)$ 的。

using T = int;
const auto cmp = [](T x, T y) { return x > y; };
unsigned f[N];
T val[N], st[20][( N >> 5 ) + 9], pre[N], suf[N];
inline T mx(T x, T y) { return cmp(x, y) ? x : y; }
inline void init(T *x, int n) {
  copy(x + 1, x + n + 1, val);
  rep (i, 0, n - 1) st[0][i >> 5] = i & 31 ? mx(st[0][i >> 5], val[i]) : val[i];
  rep (i, 1, __lg(( ( n - 1 ) >> 5 ) + 1)) rep (j, 0, ( ( n - 1 ) >> 5 ) + 1 - ( 1 << i ))
    st[i][j] = mx(st[i - 1][j], st[i - 1][j + ( 1 << ( i - 1 ) )]);
  rep (i, 0, n - 1) pre[i] = i & 31 ? mx(pre[i - 1], val[i]) : val[i];
  per (i, n - 1, 0) suf[i] = i != n - 1 && ( ~i & 31 ) ? mx(suf[i + 1], val[i]) : val[i];
  int top = 0, stk[39];
  rep (i, 0, n - 1) {
    if ( i & 31 ) f[i] = f[i - 1]; else f[i] = top = 0;
    while ( top && !cmp(val[stk[top]], val[i]) ) f[i] &= ~( 1u << ( stk[top--] & 31 ) );
    f[i] |= 1u << ( ( stk[++top] = i ) & 31 );
  }
}
inline T qry(int l, int r) {
  if ( ( --l >> 5 ) != ( --r >> 5 ) ) {
    T ret = mx(suf[l], pre[r]);
    if ( ( r >> 5 ) - ( l >> 5 ) > 1 ) {
      int t = __lg(( r >> 5 ) - ( l >> 5 ) - 1);
      ret = mx(ret, mx(st[t][( l >> 5 ) + 1], st[t][( r >> 5 ) - ( 1 << t )]));
    }
    return ret;
  }
  return val[l + __builtin_ctz(f[r] >> ( l & 31 ))];
}

谁波 rmq

• 优点：非常好写，且跑得很快
• 缺点：依赖于随机数据，查询复杂度并非 $O(1)$。

准确来说并不能放在 $O(n)-O(1)$ rmq 的博客中，但是因为他实在是太好写了，跑得太快了。

首先调用 nth_element 求出序列中前 $\frac{n}{\log n}$ 大元素，然后对这 $\frac{n}{\log n}$ 个数从大到小排序。

预处理复杂度为 nth_element 的 $O(n)$ 与排序的 $O(\frac{n}{\log n}\cdot \log n)=O(n)$。

每次查询时，从大到小枚举前 $\frac{n}{\log n}$ 个数，判断每个数是否在询问的区间中，找到即退出。

如果找不到，这样的询问数量是 $O(1)$ 的，可以直接暴力枚举，或者使用线段树查询。

在保证数据随机时，查询复杂度为期望 $O(\log n)$，且拥有一个极小的常数，甚至可以视为 $O(1)$。

int n, m, a[N], t, w[1 << 26];
pii b[N];
int qry(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return w[c];
  int mid = (l + r) >> 1;
  if (y <= mid) return qry(c << 1, l, mid, x, y);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y);
  else return max(qry(c << 1, l, mid, x, mid), qry(c << 1 | 1, mid + 1, r, mid + 1, y));
}
rep (i, 1, n) a[i] = read(), b[i] = pii(-a[i], i);
for (int i = 1; i <= n; i++) w[i + t - 1] = a[i];
per (i, t, 1) w[i] = max(w[i << 1], w[i << 1 | 1]);
nth_element(b + 1, b + B, b + n + 1), sort(b + 1, b + B + 1);
// query
rep (i, 1, B) if (b[i].se >= l && b[i].se <= r) { ans = -b[i].fi, f = 1; break; }
if (!f) ans = qry(1, 1, t, l, r);