A1236 ST表B

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

// ST 表 B（A1236）：静态数列上的区间最值查询
//
// mx[k][i] = a[i..i+2^k-1] 的最大值，mn[k][i] 是对应的最小值。
// 查询 [l,r]：k = lg(r-l+1)，用两段长度 2^k 的区间盖住 [l,r] 取最值。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int LOG = 0;
    while ((1 << (LOG + 1)) <= n) LOG++;
    vector<int> lg(n + 2, 0); // lg[i] = floor(log2(i))
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;

    vector<vector<int>> mx(LOG + 1, vector<int>(n + 2, 0));
    vector<vector<int>> mn(LOG + 1, vector<int>(n + 2, 0));
    for (int i = 1; i <= n; i++) {
        mx[0][i] = mn[0][i] = a[i]; // 长度 1 的区间
    }
    for (int k = 1; k <= LOG; k++) {
        int half = 1 << (k - 1); // 上一层区间的长度
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + half]);
            mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + half]);
        }
    }

    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        int k = lg[r - l + 1]; // 2^k <= 区间长度 < 2^(k+1)
        int span = 1 << k;
        int ans;
        if (op == 1) ans = max(mx[k][l], mx[k][r - span + 1]);
        else ans = min(mn[k][l], mn[k][r - span + 1]);
        cout << ans << "\n";
    }
    return 0;
}