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

#include <bits/stdc++.h>
using namespace std;
const int MAXN=500005*2;//初始化双倍长度，便于区间合并。
int n,q,a[MAXN],logi[MAXN],maxi[20][MAXN],mini[20][MAXN];
void solve(){
    for(int i=1;i<=n;i++){
        logi[i]=log2(i);
        //cout<<logi[i]<<" ";
    }
    maxi[0][1]=mini[0][1]=a[1];
    for(int i=0;i<20;i++){
        for(int j=1;j<=n;j++){
            if(i==0) maxi[0][j]=mini[0][j]=a[j];//单个长度空间初始化为该元素
            if(j+pow(2,i)-1<MAXN&&i!=0){
maxi[i][j]=max(maxi[i-1][j],maxi[i-1][(int)(j+pow(2,i-1))]);
mini[i][j]=min(mini[i-1][j],mini[i-1][(int)(j+pow(2,i-1))]);
//cout<<j<<" "<<j+pow(2,i)-1<<" "<<maxi[i][j]<<endl;;
            }
        }
    }
};
int op1(int l,int r){
    int log3=logi[r-l+1];
    return min(mini[log3][l],mini[log3][r-(int)pow(2,log3)+1]);
};
int op2(int l,int r){
int log3=logi[r-l+1];
    return max(maxi[log3][l],maxi[log3][r-(int)pow(2,log3)+1]);
};
int main() {
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    solve();
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        cout<<op1(l,r)<<endl;
        else
        cout<<op2(l,r)<<endl;;
    }
}
// 64 位输出请用 printf("%lld")