洛谷3865
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 const int maxn=100010; 6 int f[maxn][32],n,m,l,r; 7 void read(int &k){ 8 k=0; int f=1; char c=getchar(); 9 while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 10 while ('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 11 k*=f; 12 } 13 14 int main(){ 15 read(n); read(m); 16 for (int i=1;i<=n;i++) read(f[i][0]); 17 for (int j=1;j<=log2(n);j++) 18 for (int i=1;i<=n-(1<<j)+1;i++) 19 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 20 for (int i=1;i<=m;i++){ 21 read(l); read(r); 22 int k=log2(r-l+1); 23 printf("%d ",max(f[l][k],f[r-(1<<k)+1][k])); 24 } 25 return 0; 26 }