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

#include <bits/stdc++.h>
#include <exception>
using namespace std;
int a[5000001];
struct tree
{
    int mn,mx;
};
tree tr[20000005];
void build(int node,int left,int right)
{
    if(left==right)
    {
        tr[node].mn=a[left];
        tr[node].mx=a[right];
        return;
    }
    int mid=(left+right)/2;
    build(node*2,left,mid);
    build(node*2+1,mid+1,right);
    tr[node].mn=min(tr[node*2].mn,tr[node*2+1].mn);
    tr[node].mx=max(tr[node*2].mx,tr[node*2+1].mx);
}
int find_min(int node,int left,int right,int ql,int qr)
{
    if(ql<=left&&qr>=right)
    {
        return tr[node].mn;
    }
    else if(ql>right||qr<left)
    {
        return 1e9+1;
    }
    int mid=(left+right)/2;
    int l=find_min(node*2,left,mid,ql,qr);
    int r=find_min(node*2+1,mid+1,right,ql,qr);
    return min(l,r);
}
int find_max(int node,int left,int right,int ql,int qr)
{
    if(ql<=left&&qr>=right)
    {
        return tr[node].mx;
    }
    else if(ql>right||qr<left)
    {
        return -1e9-1;
    }
    int mid=(left+right)/2;
    int l=find_max(node*2,left,mid,ql,qr);
    int r=find_max(node*2+1,mid+1,right,ql,qr);
    return max(l,r);
}
int main() {
    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,ans;
        cin>>op>>l>>r;
        if(op==1)
        {
            ans=find_min(1,1,n,l,r);
        }
        else 
        {
            ans=find_max(1,1,n,l,r);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

这题可用线段树做，代码如上