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

此题可用线段树来解决，标准线段树模板

#include <bits/stdc++.h>
using namespace std;
const int total=1e5+7;
int a[5*total];
struct node{
    int mx;
    int mi;
}tree[total*20];

void build(int u,int l,int r){
    if(l==r){tree[u].mx=a[l],tree[u].mi=a[l];return;}
    int mid=(l+r)/2;
    build(u*2,l,mid);
    build(u*2+1,mid+1,r);
    tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
    tree[u].mi=min(tree[u*2].mi,tree[u*2+1].mi);
}

int query_max(int u,int ll,int rr,int l,int r){
    if(ll>=l && rr<=r)return tree[u].mx;
    int mid=(ll+rr)/2;
    int tem1=INT_MIN,tem2=INT_MIN;
    if(l<=mid)tem1=query_max(u*2,ll,mid,l,r);
    if(mid<r)tem2=query_max(u*2+1,mid+1,rr,l,r);
    return max(tem1,tem2);
}

int query_min(int u,int ll,int rr,int l,int r){
    if(ll>=l && rr<=r)return tree[u].mi;
    int mid=(ll+rr)/2;
    int tem1=INT_MAX,tem2=INT_MAX;
    if(l<=mid)tem1=query_min(u*2,ll,mid,l,r);
    if(mid<r)tem2=query_min(u*2+1,mid+1,rr,l,r);
    return min(tem1,tem2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)cout<<query_min(1,1,n,l,r)<<endl;
        if(op==2)cout<<query_max(1,1,n,l,r)<<endl;
    }
}