记录编号	324722	评测结果	AAAAAAAATT
题目名称	延绵的山峰	最终得分	80
用户昵称	SOBER GOOD BOY	是否通过	未通过
代码语言	C++	运行时间	2.253 s
提交时间	2016-10-18 17:59:42	内存使用	160.51 MiB

#include<cstdio>
#include<cmath>
using namespace std;

const int maxn=1000000*2;

int f[maxn][21];

int N;

int max(int a,int b){return a>b?a:b;}

int get(int l,int r)
{
    int len=r-l+1;
    int ci=0;
    while((1<<(ci+1))<=len)
    {
      ci++;
    }
    return ci;
}

int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    scanf("%d",&N);
    
    N++;  
    
    for(int i=1;i<=N;i++)scanf("%d",&f[i][0]);
    
    for(int j=1;(1<<j)<=N;j++)
    {
      for(int i=1;i+(1<<j)<=N;i++)
      f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    int Q;
    scanf("%d",&Q);
    for(int l,r,i=1;i<=Q;i++)
    {
         scanf("%d%d",&l,&r);
         l++,r++;
         int ha=get(l,r);
         printf("%d\n",max(f[l][ha],f[r-(1<<ha)+1][ha]));
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}