题解 | 【模板】静态区间最值

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

const int MAXN = 5e5 + 5;
const int LOG = 20;  // 2^20 > 5e5

int n, q;
int a[MAXN];
int stMin[MAXN][LOG];  // ST表存储最小值
int stMax[MAXN][LOG];  // ST表存储最大值
int Log[MAXN];         // 预处理log2值

// 预处理log数组
void preprocessLog() {
    Log[1] = 0;
    for (int i = 2; i <= n; i++) {
        Log[i] = Log[i / 2] + 1;
    }
}

// 构建ST表
void buildST() {
    // 初始化第一层（长度为1的区间）
    for (int i = 1; i <= n; i++) {
        stMin[i][0] = a[i];
        stMax[i][0] = a[i];
    }
    
    // 递推构建ST表
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            stMin[i][j] = min(stMin[i][j - 1], stMin[i + (1 << (j - 1))][j - 1]);
            stMax[i][j] = max(stMax[i][j - 1], stMax[i + (1 << (j - 1))][j - 1]);
        }
    }
}

// 查询区间最小值
int queryMin(int l, int r) {
    int k = Log[r - l + 1];
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}

// 查询区间最大值
int queryMax(int l, int r) {
    int k = Log[r - l + 1];
    return max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
}

int main() {
    // 加速IO
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 预处理
    preprocessLog();
    buildST();
    
    // 处理查询
    while (q--) {
        int op, l, r;
        cin >> op >> l >> r;
        
        if (op == 1) {
            cout << queryMin(l, r) << "\n";
        } else {
            cout << queryMax(l, r) << "\n";
        }
    }
    
    return 0;
}