- #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;
- }
| 
楼主
