题解 | 【模板】静态区间最值 ： 分块！

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

const int N= 5e5+5,inf=1e9+7;

int n,q,len;

int a[N];
int mx[N],mn[N];

void solve(){
    cin>>n>>q;
    len=ceil(sqrt(n));
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=n/len;i++){
        mx[i]=-inf;
        mn[i]=inf;
    }
    for(int i=1;i<=n;i++){
        mx[i/len]=max(mx[i/len],a[i]);
        mn[i/len]=min(mn[i/len],a[i]);
    }
    int l,r,op;
    while(q--){
        cin>>op>>l>>r;
        if(op==1){
            int res=inf;
            if(l/len==r/len){
                for(int i=l;i<=r;i++){
                    res=min(res,a[i]);
                }
            }else {
                for(int j=l/len+1;j<r/len;j++){
                    res=min(res,mn[j]);
                }
                for(int j=l;j<(l/len+1)*len;j++){
                    res=min(res,a[j]);
                }
                for(int j=r/len*len;j<=r;j++){
                    res=min(res,a[j]);
                }
            }
            cout<<res<<"\n";
        }else {
            int res=-inf;
            if(l/len==r/len){
                for(int i=l;i<=r;i++){
                    res=max(res,a[i]);
                }
            }else{
                for(int j=l/len+1;j<r/len;j++){
                    res=max(res,mx[j]);
                }
                for(int j=l;j<(l/len+1)*len;j++){
                    res=max(res,a[j]);
                }
                for(int j=r/len*len;j<=r;j++){
                    res=max(res,a[j]);
                }
            }
            cout<<res<<"\n";
        }
    } 

}

int main(){
    solve();
}