【模板】ST 表 RMQ 问题

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,m;
int f[maxn][20];
int Log[maxn];
void llog(){for (int i=2;i<=n;i++) Log[i]=Log[i>>1]+1;}
void ST()
{for (int j=1;j<=Log[n];j++){for (int i=1;i<=n-(1<<j)+1;i++){f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);}}
}
inline void read(int &x)
{// 快读不然被卡TLEchar ch=getchar();int f=1;x=0;while(!isdigit(ch) && ch^'-') ch=getchar();if(ch=='-') f=-1,ch=getchar();while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();x*=f;
}
int main()
{read(n),read(m);llog();for (int i=1;i<=n;i++) read(f[i][0]);ST();while(m--){int x,y;read(x),read(y);int k=Log[y-x+1];cout << max(f[x][k],f[y-(1<<k)+1][k]) << '\n';// '\n'不然也被卡}return 0;
}