#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N],n,f[N][30],Log2[N];
//f[i][p]表示从第i个点开始的2^p个数的最值
//即区间 [i,i+2^p-1] 的最值
void init() {//nlogn预处理
for(int i=1; i<=n; i++)f[i][0]=a[i];//f[i][0]为本身
for(int p=1; (1<<p)<=n; p++) {//防出界
for(int i=1; i+(1<<p)-1<=n; i++) {//第i个点控制的区间到1+(1<<p)-1，防出界
f[i][p]=max(f[i][p-1],f[i+(1<<(p-1))][p-1]);
//f[i][p]的最值由前半段f[i][p-1]和后半段f[i+pow(2,p-1)][p-1]得来
}
}
int t=0;//log2打表
for(int i=0;i<=n;i++){
while((1<<(t+1))<=i)t++;
Log2[i]=t;
}
}
int query(int l,int r){
int k=Log2[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
int m,l,r;
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
init();
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
printf("%d",query(l,r));
}
return 0;
}
| 
楼主
标题置顶
标题高亮
