48 lines
921 B
C++
48 lines
921 B
C++
#include <algorithm>
|
|
#include <cctype>
|
|
#include <cmath>
|
|
#include <cstdio>
|
|
#include <iostream>
|
|
using namespace std;
|
|
|
|
int readint();
|
|
const int MAX_N = 1e5+5;
|
|
const int MAX_LN = 20;
|
|
int s[MAX_N][MAX_LN];
|
|
int m,n;
|
|
int l2[MAX_N];
|
|
|
|
int main(){
|
|
n=readint(),m=readint();
|
|
l2[1]=0;
|
|
for(int i=2;i<=n;i++){
|
|
l2[i]=l2[i/2]+1;
|
|
}
|
|
for(int i=1;i<=n;i++){
|
|
s[i][0]=readint();
|
|
}
|
|
for (int j=1;j<=l2[n]; j++) {
|
|
for(int i=1;i<=n-(1<<j)+1;i++){
|
|
s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
|
|
}
|
|
}
|
|
for(int i=1;i<=m;i++){
|
|
const int l=readint(),r=readint();
|
|
int j = l2[r-l+1];
|
|
cout<<max(s[l][j],s[r-(1<<j)+1][j])<<endl;
|
|
}
|
|
}
|
|
|
|
int readint(){
|
|
int x=0,w=1;
|
|
char ch=0;
|
|
while(!isdigit(ch)){
|
|
if(ch=='-')w=-1;
|
|
ch=getchar();
|
|
}
|
|
while(isdigit(ch)){
|
|
x=x*10+(ch-'0');
|
|
ch=getchar();
|
|
}
|
|
return x*w;
|
|
} |