记录编号	159010	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.478 s
提交时间	2015-04-18 21:56:00	内存使用	15.57 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MAXN=1000010;
const int MAX_INT=0x7fffffff;
const int MAXT=110;

int trees[MAXN*4];

int build_tree(int dir,int l,int r)
{
        if(l==r) {scanf("%d",&trees[dir]);return trees[dir];}
        int mid=(l+r)/2;
        int tl=build_tree(dir*2,l,mid);
        int tr=build_tree(dir*2+1,mid+1,r);
        return trees[dir]=max(tl,tr);
}

int tree_find(int dir,int l,int r,int tl,int tr)
{
        if(tl<=l&&tr>=r) return trees[dir];
        int mid=(l+r)/2;
        if(tr<=mid) return tree_find(dir*2,l,mid,tl,tr);
        else if(tl>mid) return tree_find(dir*2+1,mid+1,r,tl,tr);
        else
        {
                int t1=tree_find(dir*2,l,mid,tl,tr);
                int t2=tree_find(dir*2+1,mid+1,r,tl,tr);
                return max(t1,t2);
        }
}

int main()
{
        ///freopen("sample_data.in","r",stdin);
        freopen("climb.in","r",stdin);
        freopen("climb.out","w",stdout);
        memset(trees,-1,sizeof(trees));
        int n;scanf("%d",&n);
        build_tree(1,0,n);
        int Q;scanf("%d",&Q);
        for(int i=0;i<Q;i++)
        {
                int tl,tr;
                scanf("%d%d",&tl,&tr);
                int t=tree_find(1,0,n,tl,tr);
                printf("%d\n",t);
        }
        return 0;
}