RT，正解复杂度（疑似）+O2+inout优化+log预处理优化 80pts？

RID=124954653

#include<bits/stdc++.h>
using namespace std;
static int i,j,n,m,dp[1000001][61] = {0};
inline int po(int k){
	return 1<<k;
}
int logn[1000001] = {0};
void pre(){
	logn[1] = 0,logn[2] = 1;
	for(int i = 3;i<=1000001;i++)logn[i]=logn[i/2]+1;
}
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 main(){
	freopen("P3865_4.in","r",stdin);
	pre();
	cout<<"preload OK"<<endl;
	cout.tie();
	n = read();
	m = read();
	for(i = 1;i<=n;i++){
		dp[i][0] = read();
	}
	cout<<"init OK"<<endl;
	for(j = 1;j<=25;j++){
		for(i = 1;i+(1<<j)-1<=n;i++){
			//cout<<i<<" "<<j<<" is OK."<<endl;
			dp[i][j] = max(dp[i][j-1],dp[i+po(j-1)][j-1]);
		}
	}
	register int l,r;
	while(m--){
		l = read();r = read();
		cout<<max(dp[l][logn[r-l+1]],dp[r-po(logn[r-l+1])+1][logn[r-l+1]])<<endl;
	}
	return 0;
}