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

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
const int N=5e5+10;
const int M=2e5+10;
// const int mod = 1000000007;
const int mod = 998244353;
//随机化
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 1000000000);
// cout<<fixed<<setprecision(10);

ll a[N];
struct seg{
    int l,r;
    ll mx,mi;
    ll lz;
}tr[N<<2];
void pushup(int p){
    tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
    tr[p].mi=min(tr[p<<1].mi,tr[p<<1|1].mi);
}
void pushdown(int p){
    if(tr[p].lz){
        ll c=tr[p].lz;
        tr[p<<1].mx+=c;
        tr[p<<1].mi+=c;
        tr[p<<1].lz+=c;
        tr[p<<1|1].mx+=c;
        tr[p<<1|1].mi+=c;
        tr[p<<1|1].lz+=c;
        tr[p].lz=0;
    }
}
void build(int p,int l,int r){
    tr[p].l=l;
    tr[p].r=r;
    if(l==r){
        tr[p].mx=tr[p].mi=a[l];
        tr[p].lz=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void add(int p,int l,int r,int k){
    if(tr[p].r<l||r<tr[p].l) return ;
    if(l<=tr[p].l&&tr[p].r<=r){
        tr[p].mx+=k;
        tr[p].mi+=k;
        tr[p].lz+=k;
        return ;
    }
    pushdown(p);
    add(p<<1,l,r,k);
    add(p<<1|1,l,r,k);
    pushup(p);
}   
pair<ll,ll> query(int p,int l,int r){
    if(tr[p].r<l||r<tr[p].l)return {1e18,-1e18};
    if(l<=tr[p].l&&tr[p].r<=r){
        return {tr[p].mi,tr[p].mx};
    }
    pushdown(p);
    auto L=query(p<<1,l,r);
    auto R=query(p<<1|1,l,r);
    return {min(L.first,R.first),max(L.second,R.second)};
}
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r).first<<'\n';
        }else if(op==2){
            int l,r;
            cin>>l>>r;
            cout<<query(1,l,r).second<<'\n';
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--){
        solve();
    }
    return 0;
}

线段树爆冲过去就完了