#P1042. 静态RMQ[ST表模板]

题意是：给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。

ST表的基本功能是对区间进行查询，其核心使用的是倍增的思想

f[i][k]:意思是从第i个数开始往后2^k个数

f[i][k]=max(f[i][k-1],f[i+2^k-1][k-1])

求【l,r】区间 max(f[i][k],f[r-2^k+1][k])

#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
int f[N][30];
int n,m;
void init(){
	for(int i=1;i<=n;i++){
		f[i][0]=a[i];
	}
	for(int k=1;k<=20;k++){
		for(int i=1;i+(1<<k-1)<=n;i++){
			f[i][k]=max(f[i][k-1],f[i+(1<<k-1)][k-1]);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	init();
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		int len=r-l+1;
		int k=log2(len);
		int ans=max(f[l][k],f[r-(1<<k)+1][k]);
		cout<<ans<<"\n";
	}
	return 0;
}