TLE49butST表

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[200005],ST[200005][20];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int find(int l,int r){
	int k=log2(r-l+1);
	return max(ST[l][k],ST[r-(1<<k)+1][k]);
}
signed main(){
	cin>>n>>m;
	for (int i=1;i<=n;i++)a[i]=read();
	int lg=log2(n);
	for (int i=1;i<=n;i++)ST[i][0]=a[i];
	for (int j=1;j<=lg;j++) for (int i=1;i<=n-(1<<(j-1))+1;i++) ST[i][j]=max(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
	for (int i=1;i<=m;i++){
		int ll,rr;
		cin>>ll>>rr;
		cout<<find(ll,rr)<<endl;
	}
}