Todo List

https://dmoj.ca/problem/macs2p3 「7」

https://dmoj.ca/problem/yac9p3 【10】

https://dmoj.ca/problem/sac22cc4p4 【10】

https://dmoj.ca/problem/ccc20s3 【12】

一、先搞懂两个核心概念

1. RMQ (Range Maximum/Minimum Query)

翻译：区间最值查询

• 给你一个不会修改的静态数组
• 多次提问：「数组下标 l 到 r 之间，最大的数是多少？」
• 这就是 RMQ 问题

2. 稀疏表 (Sparse Table)

解决 RMQ 问题的最优算法（针对静态数组）：

• 预处理：O(n log n) （只做一次）
• 每次查询：O(1) （秒出答案）
• 完全适配你的题目：需要无数次查询环形区间的最大值

---

二、核心原理

稀疏表用了倍增思想：

1. 提前算好：从每个位置开始，长度为 1、2、4、8...（2 的次方）的区间的最大值；
2. 查询任意区间 [l, r] 时，把这个区间拆成两个重叠的、2 的次方长度的小区间；
3. 两个小区间的最大值，就是整个区间的最大值。

---

三、手把手数值例子

我们用一个极简数组演示：

数组 a = [3, 1, 4, 2, 5] （下标：0 1 2 3 4，长度 n=5）

第一步：预处理稀疏表

我们定义 st[k][i] = 从下标 i 开始，长度为 2^k 的区间的最大值。

1. k=0（长度 = 1，2⁰=1）：就是元素本身 st [0] = [3, 1, 4, 2, 5]
2. k=1（长度 = 2，2¹=2）：每 2 个元素取最大 st [1][0] = max (3,1)=3 st [1][1] = max (1,4)=4 st [1][2] = max (4,2)=4 st [1][3] = max (2,5)=5
3. k=2（长度 = 4，2²=4）：每 4 个元素取最大 st [2][0] = max (st [1][0], st [1][2]) = max (3,4)=4 st [2][1] = max (st [1][1], st [1][3]) = max (4,5)=5
4. k≥3 超出数组长度，停止

第二步：查询演示（3 个经典例子）

例子 1：查询区间 [1, 3] （元素：1,4,2 → 最大值 = 4）

1. 区间长度 = 3-1+1 = 3
2. 找最大的 k 满足 2ᵏ ≤ 3 → k=1（2¹=2）
3. 拆成两个区间：[1,2] 和 [2,3]
4. 最大值 = max (st [1][1], st [1][2]) = max (4,4) = 4 ✔️

例子 2：查询区间 [0,4] （整个数组 → 最大值 = 5）

1. 长度 = 5 → k=2（2²=4）
2. 拆成 [0,3] 和 [1,4]
3. 最大值 = max (st [2][0], st [2][1]) = max (4,5) = 5 ✔️

例子 3：查询区间 [2,4] （元素：4,2,5 → 最大值 = 5）

1. 长度 = 3 → k=1
2. 拆成 [2,3] 和 [3,4]
3. 最大值 = max (st [1][2], st [1][3]) = max (4,5) = 5 ✔️

---

四、极简可运行代码（C++）

这是精简版稀疏表，专门用来查区间最大值

cpp

运行

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

// 稀疏表：区间最大值查询
struct SparseTable {
    vector<vector<ll>> st;
    int LOG;

    // 构建稀疏表
    void build(vector<ll>& a) {
        int n = a.size();
        LOG = 20; // 足够用的层数
        st.resize(LOG, vector<ll>(n));
        
        // k=0：初始状态
        for (int i = 0; i < n; i++) st[0][i] = a[i];
        
        // 倍增预处理
        for (int k = 1; k < LOG; k++)
            for (int i = 0; i + (1 << k) <= n; i++)
                st[k][i] = max(st[k-1][i], st[k-1][i + (1 << (k-1))]);
    }

    // 查询 [l, r] 的最大值
    ll query(int l, int r) {
        int len = r - l + 1;
        int k = __lg(len); // 自动找最大的k
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

int main() {
    // 测试数组：[3,1,4,2,5]
    vector<ll> a = {3,1,4,2,5};
    SparseTable st;
    st.build(a);

    // 测试3个查询
    cout << "区间[1,3]最大值：" << st.query(1,3) << endl;
    cout << "区间[0,4]最大值：" << st.query(0,4) << endl;
    cout << "区间[2,4]最大值：" << st.query(2,4) << endl;
    return 0;
}

运行结果

plaintext

区间[1,3]最大值：4
区间[0,4]最大值：5
区间[2,4]最大值：5

和我们手动算的完全一致！

#include <bits/stdc++.h>
using namespace std;

struct SparseTable {
    int n, K;
    vector<int> lg;
    vector<vector<int>> st;

    SparseTable(const vector<int>& a) {
        n = (int)a.size();
        K = __lg(n) + 1;
        lg.resize(n + 1);
        for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;

        st.assign(K, vector<int>(n));
        st[0] = a;

        for (int k = 1; k < K; ++k) {
            int len = 1 << k;
            int half = len >> 1;
            for (int i = 0; i + len <= n; ++i) {
                st[k][i] = max(st[k - 1][i], st[k - 1][i + half]);
            }
        }
    }

    int query(int l, int r) {
        int k = lg[r - l + 1];
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    SparseTable sp(a);

    while (q--) {
        int l, r;
        cin >> l >> r;
        --l; --r;                  // 如果输入是 1-based
        cout << sp.query(l, r) << '\n';
    }
    return 0;
}