76 lines
1.5 KiB
C++
76 lines
1.5 KiB
C++
|
#include<bits/stdc++.h>
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
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;
|
||
|
|
}
|
||
|
|
|
||
|
|
#define int long long
|
||
|
|
|
||
|
|
#ifdef OIPRINT
|
||
|
|
#define PRINT_VALUE(v){cout<<"[DEBUG]: "<<#v<<" :"<<(v)<<endl;}
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef OIPRINT
|
||
|
|
#define PRINT_VALUE(v)
|
||
|
|
#endif
|
||
|
|
|
||
|
|
inline int max(int a,int b){
|
||
|
|
return a>b?a:b;
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
const int MAX_N = 1e5+5,MAX_K=17;
|
||
|
|
int n,m,s[MAX_N][MAX_K],l[MAX_N];
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
signed main(){
|
||
|
|
// cin.sync_with_stdio(false);
|
||
|
|
// cin.tie(0);
|
||
|
|
// cin>>n>>m;
|
||
|
|
n=read();
|
||
|
|
m=read();
|
||
|
|
PRINT_VALUE(n);
|
||
|
|
PRINT_VALUE(m);
|
||
|
|
|
||
|
|
l[1]=0;
|
||
|
|
// for(int i=2;i<=n;i++){
|
||
|
|
// l[i]=l[i/2]+1;
|
||
|
|
// }
|
||
|
|
for(int i=1;i<=n;i++){
|
||
|
|
// cin>>s[i][0];
|
||
|
|
s[i][0]=read();
|
||
|
|
PRINT_VALUE(s[i][0]);
|
||
|
|
if(i!=1)l[i]=l[i/2]+1;
|
||
|
|
}
|
||
|
|
int k=l[n]+1;
|
||
|
|
for(int j=1;j<=k;j++){
|
||
|
|
for(int i=1;i-1+(1<<j)<=n;i++){
|
||
|
|
PRINT_VALUE(i);
|
||
|
|
PRINT_VALUE(j);
|
||
|
|
s[i][j]=max(s[i][j-1],s[i+(1<<(j-1))][j-1]);
|
||
|
|
PRINT_VALUE(s[i][j]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
for(int i=1;i<=m;i++){
|
||
|
|
int le,r;
|
||
|
|
// cin>>le>>r;
|
||
|
|
le=read();
|
||
|
|
r=read();
|
||
|
|
PRINT_VALUE(le-r+1);
|
||
|
|
int j=l[r-le+1];
|
||
|
|
PRINT_VALUE(le);
|
||
|
|
PRINT_VALUE(r);
|
||
|
|
PRINT_VALUE(j);
|
||
|
|
// PRINT_VALUE(s[le][j]);
|
||
|
|
// PRINT_VALUE(s[r-(1<<j)+1][j]);
|
||
|
|
// PRINT_VALUE(r-(1<<j)+1)
|
||
|
|
cout<<max(s[le][j],s[r-(1<<j)+1][j])<<endl;
|
||
|
|
}
|
||
|
|
}
|