形式化题目

给定长度为 $N$ 的静态数列 $a_1, a_2, \dots, a_N$ 和 $M$ 个询问。每个询问给出闭区间端点 $1 \leqslant X \leqslant Y \leqslant N$，要求回答该区间的最大值：

所有询问期间数列不发生修改，即静态区间最值查询（RMQ）。

正解

思路

朴素做法与瓶颈。 每次询问从 $X$ 扫到 $Y$ 维护最大值，单次 $O(N)$，总代价 $O(NM)$， 最坏 $10^{11}$ 次比较。瓶颈在于不同询问大量覆盖相同子区间，朴素做法没有复用任何结果； 而 $M \gg N$，必须让单次询问降到 $O(1)$。

关键观察：$\max$ 是幂等的。 $\max(S \cup S) = \max(S)$，区间允许重叠地拆成两段再合并。 于是只要备齐"长度为 $2$ 的幂"的区间的最大值，任意长度的区间都能用两段拼出来。

倍增建表。 长度 $2^k$ 的区间恰好由两个长度 $2^{k-1}$ 的区间拼成，因此可以逐层递推：

其中 $st[k][i]$ 表示从 $i$ 开始、长度 $2^k$ 的区间最大值（0-based 下标）。下表是样例数列 $[3, 2, 4, 5, 6, 8, 1, 2, 9, 7]$ 的完整 ST 表，行是层 $k$，列是起点 $i$：

观察点：第 $k$ 行第 $i$ 列由第 $k-1$ 行的第 $i$ 列和第 $i + 2^{k-1}$ 列取 max 得到， 例如 $st[2][0] = \max(st[1][0], st[1][2]) = \max(3, 5) = 5$。层数到 $2^k > N$ 为止， 每层比上一层短一半，总规模 $O(N \log N)$。

查询两段覆盖。 对询问 $[X, Y]$（换算成 0-based 的 $[l, r]$），令 $len = r - l + 1$、 $k = \lfloor \log_2 len \rfloor$，答案取两段的 max：

因为 $2^k \leqslant len < 2^{k+1}$，每块长度 $2^k \leqslant len$ 所以都落在询问区间内； 两块相交等价于 $l + 2^k - 1 \geqslant r - 2^k + 1$，即 $2^{k+1} \geqslant len + 1$， 由 $len < 2^{k+1}$ 保证，故并集恰好是 $[l, r]$；重叠部分因幂等性不影响答案。用样例验证： 询问 $[1, 4]$（0-based $0..3$，$len = 4$，$k = 2$）两块都是 $st[2][0] = 5$，答案 $5$； 询问 $[3, 8]$（0-based $2..7$，$len = 6$，$k = 2$）取 $st[2][2] = 8$ 与 $st[2][4] = 8$， 两块分别覆盖 $2..5$ 和 $4..7$，重叠但并起来恰是 $2..7$，答案 $8$。

查对数与查表。 $\lfloor \log_2 len \rfloor$ 用 logs[len] = logs[len >> 1] + 1 一次性线性预处理， 查询时不做浮点运算；$M$ 高达 $10^6$，输出先攒进列表最后一次性写出。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 17:08
# update_at: 2026-09-30 17:08

import sys
from collections.abc import Iterator


def build_st(a: list[int]) -> list[list[int]]:
    """ST 表：st[k][i] = a[i..i+2^k-1] 的最大值，由下一层两个半段合并。"""
    st = [a]
    span = 2  # 当前层区间长度
    while span <= len(a):
        prev = st[-1]
        half = span >> 1
        st.append([max(prev[i], prev[i + half]) for i in range(len(a) - span + 1)])
        span <<= 1
    return st


def solve() -> None:
    data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    a = [next(data) for _ in range(n)]  # 题目给的是 1-based 下标

    st = build_st(a)

    # logs[x] = floor(log2(x))：由 x//2 的结果递推，避免每条询问做浮点对数
    logs = [0] * (n + 1)
    for i in range(2, n + 1):
        logs[i] = logs[i >> 1] + 1

    out: list[str] = []
    append = out.append
    for _ in range(m):
        l, r = next(data) - 1, next(data) - 1
        k = logs[r - l + 1]                       # 不超过区间长度的最大 2 的幂
        # 两段等长 2^k 允许重叠：max 重复取元素不影响结果
        append(str(max(st[k][l], st[k][r - (1 << k) + 1])))

    sys.stdout.write('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:11
 * update_at: 2026-10-05 07:11
 */

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005;   // 数列长度上限
const int LOG = 17;        // 2^17 > 1e5，层数足够覆盖所有区间长度

int n, m;
int a[MAXN];               // 原数列，1-based
int st[LOG][MAXN];         // st[k][i]：从 i 开始、长度 2^k 的区间最大值
int logs[MAXN];            // logs[x] = floor(log2(x))，预处理避免查询时算浮点对数

// 求 floor(log2(x))（x >= 1），只用在建表前确定层数
int log2_floor(int x) {
    int res = 0;
    while ((1 << (res + 1)) <= x) res++;
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 建表：第 0 层是长度 1 的区间，就是原数列本身
    int K = log2_floor(n); // 最大有用的层号，2^K <= n < 2^(K+1)
    for (int i = 1; i <= n; i++) st[0][i] = a[i];
    // 长度 2^k 的区间由两个长度 2^(k-1) 的半段取 max 拼成
    for (int k = 1; k <= K; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

    // logs 递推：x 的一半的对数再加一，线性预处理，查询 O(1)
    logs[1] = 0;
    for (int x = 2; x <= n; x++) logs[x] = logs[x >> 1] + 1;

    // 每条询问：两段等长 2^k 区间允许重叠地覆盖 [l, r]
    // max 幂等，重叠部分重复取不影响答案
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        int k = logs[r - l + 1]; // 不超过区间长度的最大 2 的幂
        printf("%d\n", max(st[k][l], st[k][r - (1 << k) + 1]));
    }
    return 0;
}

复杂度

• 时间：建表 $O(N \log N)$，查询每条 $O(1)$，合计 $O(N \log N + M)$。
• 空间：$O(N \log N)$ 个表项，$N = 10^5$ 时约 $1.7 \times 10^6$ 个整数。 本题 Python 实现实测峰值约 223 MB（主要是一次性读入切分出的数百万个字节串）， 超过题面 128 MB 内存限制；按仓库的 python-oj-short 规则允许 MLE， C++ 用静态 int 数组实现同一算法约数 MB 即可。

总结

静态 RMQ 的标准解法是 ST 表：$\max$ 幂等 + 长度按 $2$ 的幂倍增递推，使任意区间都能 用两块可重叠的 $2$ 幂区间覆盖，从而 $O(N \log N)$ 预处理、$O(1)$ 回答每次询问， 恰好匹配本题 $N \leqslant 10^5$、$M \leqslant 10^6$ 的规模。