P3865 【模板】ST表

这是一道ST表经典题——静态区间最大值

给定一个长度为 NN 的数列，和 MM 次询问，求出每一次询问的区间内数字的最大值。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define it register int
#define inf 0x3f3f3f3f
#define lowbit(x) (x)&(-x)
#define mem(a,b) memset(a,b,sizeof(a))
#define modd 998244353
const int maxn=1e6+10;
int st[maxn][20],n,m,k,a[maxn];
il void makest(){
    for(it i=1;i<=n;i++){
        st[i][0]=a[i];
    }
    for(it i=1;(1<<i)<=n;i++){
        for(it j=1;j+(1<<i)-1<=n;j++){
            st[j][i]=max(st[j][i-1],st[j+(1<<i-1)][i-1]);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(it i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    makest();
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        int k=log2(r-l+1);
        printf("%d
",max(st[l][k],st[r-(1<<k)+1][k]));
    }
    return 0;
}