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

#include <cstdio>
#include <initializer_list>
#include <iostream>
#include<algorithm>
using namespace std;
const int N=5e5+10;
const int LOGN=20;
int fmin[N][LOGN];//第几个数 包含的2的几次方
int fmax[N][LOGN];
int log[N];//储存log2 
int a[N];
void inti(int n){
    log[1]=0;
    for(int i=2;i<=n;i++)log[i]=log[i/2]+1;
    for(int i=1;i<=n;i++){
        fmin[i][0]=a[i];
        fmax[i][0]=a[i];
    }
    for(int j=1;j<=log[n];j++){
        for(int i=1;i + (1<<j)-1 <=n;i++){//已知起点求终点 找这一块的尾
            fmin[i][j]=min(fmin[i][j-1],fmin[i+(1<<(j-1))][j-1]);
            fmax[i][j]=max(fmax[i][j-1],fmax[i+(1<<(j-1))][j-1]);//状态的偏移 找下一块的头 从左边状态转移到右边状态
        }
    }
}
int  query(int l,int r,int op){
    int k=log[r-l+1];
    if(op==1)return min(fmin[l][k],fmin[r-(1<<k)+1][k]);//已知终点求起点
    else return max(fmax[l][k],fmax[r-(1<<k)+1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    inti(n);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        cout<<query(l,r,op)<<"\n";
    }
    return 0;
}

用st表 倍增的思想 把一个大的区间分成两半去求

在比较大小时 我们只要做到不漏即可 不必要求不重