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

#include <iostream>
using namespace std;
int a[500050];
int st_min[20][500050];
int st_max[20][500050];
int log_table[500050];
int main() {
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    log_table[1]=0;
    for(int i=2;i<=n;++i)log_table[i]=log_table[i>>1]+1;
    for(int i=1;i<=n;++i){
        st_min[0][i]=a[i];
        st_max[0][i]=a[i];
    }
    for(int k=1;(1<<k)<=n;++k){
        for(int i=1;i+(1<<k)-1<=n;++i){
            st_min[k][i]=min(st_min[k-1][i],st_min[k-1][i+(1<<(k-1))]);
            st_max[k][i]=max(st_max[k-1][i],st_max[k-1][i+(1<<(k-1))]);
        }
    }
    while(q--){
        int op;cin>>op;
        int l,r;cin>>l>>r;
        if(op==1){
            int k=log_table[r-l+1];
            cout<<min(st_min[k][l],st_min[k][r-(1<<k)+1])<<endl;
        }else{
            int k=log_table[r-l+1];
            cout<<max(st_max[k][l],st_max[k][r-(1<<k)+1])<<endl;
        }
    }
}
// 64 位输出请用 printf("%lld")