【Luogu】P3865ST表模板（ST表）

　　题目链接

　　本来准备自己yy一个倍增来着，然而一看要求O1查询就怂了。

　　ST表模板。放上代码。

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cmath>

inline long long max(long long a,long long b){    return a>b?a:b;    }

inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}
    

int s[100010][31];

int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;++i)    s[i][0]=read();
    for(int i=1;(1<<i)<=n;++i)
        for(int j=1;j+(1<<(i-1))<=n;++j)    s[j][i]=max(s[j][i-1],s[j+(1<<(i-1))][i-1]);
    for(int i=1;i<=m;++i){
        int from=read(),to=read();
        int f=log2(to-from+1);
        printf("%d
",max(s[from][f],s[to-(1<<f)+1][f]));
    }
    return 0;
}