(2) （ RMQ 区间最值问题） 给定序列 $a_0,\cdots,a_{n-1},$ $m$ 次询问，每次询问给定 $l,r$，求 $\max \{a_l,\ ...,a_r\}$。

为了解决该问题，有一个算法叫 the Method of Four Russians ，其时间复杂度为 $O(n+m)$ ，步骤如下：

• 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。

• 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。

• 注意新的问题为 $\pm1$ RMQ，即相邻两点的深度差一定为 $1$。

下面解决这个 $\pm1$ RMQ 问题，“序列”指 Euler 序列：

• 设 $t$ 为 Euler 序列长度。取 $b=\lceil \frac{\log_2 t}{2} \rceil$ 将序列每 $b$ 个分为一大块， 使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 $O(\frac{t}{b}\log t)=O(n)$。

• （重点） 对于一个块内的 RMQ 问题，也需要 $O(1)$ 的算法。由于差分数组 $2^{b-1}$ 种，可以预处理出所有情况下的最值位置，预处理复杂度 $O(b2^b)$，不超过 $O(n)$。

• 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。

试补全程序。

1#include <iostream>2#include <cmath>3 4using namespace std;5 6const int MAXN = 100000, MAXT = MAXN << 1;7const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;8 9struct node {10    int val;11    int dep, dfn, end;12    node *son[2]; // son[0], son[1] 分别表示左右儿子13} T[MAXN];14 15int n, t, b, c, Log2[MAXC + 1];16int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];17node *root, *A[MAXT], *Min[MAXL][MAXC];18 19void build() { // 建立 Cartesian 树20    static node *S[MAXN + 1];21    int top = 0;22    for (int i = 0; i < n; i++) {23        node *p = &T[i];24        while (top && S[top]->val < p->val)25            ①;26        if (top)27            ②;28        S[++top] = p;29    }30    root = S[1];31}32 33void DFS(node *p) { // 构建 Euler 序列34    A[p->dfn = t++] = p;35    for (int i = 0; i < 2; i++)36        if (p->son[i]) {37            p->son[i]->dep = p->dep + 1;38            DFS(p->son[i]);39            A[t++] = p;40        }41    p->end = t - 1;42}43 44node *min(node *x, node *y) {45    return ③ ? x : y;46}47 48void ST_init() {49    b = (int)(ceil(log2(t) / 2));50    c = t / b;51    Log2[1] = 0;52    for (int i = 2; i <= c; i++)53        Log2[i] = Log2[i >> 1] + 1;54    for (int i = 0; i < c; i++) {55        Min[0][i] = A[i * b];56        for (int j = 1; j < b; j++)57            Min[0][i] = min(Min[0][i], A[i * b + j]);58    }59    for (int i = 1, l = 2; l <= c; i++, l <<= 1)60        for (int j = 0; j + l <= c; j++)61            Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);62}63 64void small_init() { // 块内预处理65    for (int i = 0; i <= c; i++)66        for (int j = 1; j < b && i * b + j < t; j++)67            if (④)68                Dif[i] |= 1 << (j - 1);69    for (int S = 0; S < (1 << (b - 1)); S++) {70        int mx = 0, v = 0;71        for (int i = 1; i < b; i++) {72            ⑤;73            if (v < mx) {74                mx = v;75                Pos[S] = i;76            }77        }78    }79}80 81node *ST_query(int l, int r) {82    int g = Log2[r - l + 1];83    return min(Min[g][l], Min[g][r - (1 << g) + 1]);84}85 86node *small_query(int l, int r) { // 块内查询87    int p = l / b;88    int S = ⑥;89    return A[l + Pos[S]];90}91 92node *query(int l, int r) {93    if (l > r)94        return query(r, l);95    int pl = l / b, pr = r / b;96    if (pl == pr) {97        return small_query(l, r);98    } else {99        node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r));100        if (pl + 1 <= pr - 1)101            s = min(s, ST_query(pl + 1, pr - 1));102        return s;103    }104}105 106int main() {107    int m;108    cin >> n >> m;109    for (int i = 0; i < n; i++)110        cin >> T[i].val;111    build();112    DFS(root);113    ST_init();114    small_init();115    while (m--) {116        int l, r;117        cin >> l >> r;118        cout << query(T[l].dfn, T[r].dfn)->val << endl;119    }120    return 0;121}