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

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6+10;
int q,n;
int a[N];
int mx[N],mn[N];

void up(int i)
{
    mx[i] = max(mx[i<<1],mx[i<<1|1]);
    mn[i] = min(mn[i<<1],mn[i<<1|1]);
}

int get_mn(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&jobr>=r)
    {
        return mn[i];
    }
    else 
    {
        int mid = (l+r)>>1;
        int ans = INT_MAX;
        if(mid>=jobl)
        {
            ans = min(ans,get_mn(jobl,jobr,l,mid,i<<1));
        }
        if(mid<jobr)
        {
            ans = min(ans,get_mn(jobl,jobr,mid+1,r,i<<1|1));
        }
        return ans;
    }
}


int get_mx(int jobl,int jobr,int l,int r,int i)
{
    if(jobl<=l&&jobr>=r)
    {
        return mx[i];
    }
    else 
    {
        int mid = (l+r)>>1;
        int ans = INT_MIN;
        if(mid>=jobl)
        {
            ans = max(ans,get_mx(jobl,jobr,l,mid,i<<1));
        }
        if(mid<jobr)
        {
            ans = max(ans,get_mx(jobl,jobr,mid+1,r,i<<1|1));
        }
        return ans;
    }
}


void build(int l,int r,int i)
{
    if(l==r)
    {
        mx[i]=mn[i]=a[l];
    }
    else 
    {
        int mid = (l+r)>>1;
        build(l,mid,i<<1);
        build(mid+1,r,i<<1|1);
        up(i);
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    build(1,n,1);

    while(q--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1)
        {
            cout<<get_mn(l,r,1,n,1)<<'\n';
        }
        else 
        {
            cout<<get_mx(l,r,1,n,1)<<'\n';
        }
    }
    
    return 0;
}

线段树板子