记录编号	166149	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.516 s
提交时间	2015-06-14 11:23:35	内存使用	38.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
struct TREE{
	int sum;
	int l;
	int r;
	TREE *lc,*rc;
	TREE():sum(-0x7f){}
};

int n,m,a[10000000];
int ans;

void build(TREE *p,int l,int r){
	//cout<<l<<" "<<r<<endl;
	p->l=l;
	p->r=r;
	if (l+1==r)
	{
		p->sum=a[l];
		p->lc=NULL;
		p->rc=NULL;
		return;
	}
	else if (l+1<r)
	{
		p->lc=new TREE;
		p->rc=new TREE;
		build(p->lc,l,(l+r)/2);
		build(p->rc,(l+r)/2,r);
		p->sum=max(p->lc->sum,p->rc->sum);
		return;
	}
	return;
}

int Q(TREE*p,int l,int r)
{
	if (l<=p->l&&p->r<=r)
	 return ans=max(ans,p->sum);
	else
	{
		if (l<(p->l+p->r)/2)
		 ans=max(ans,Q(p->lc,l,r));
		if (r>(p->l+p->r)/2)
		 ans=max(ans,Q(p->rc,l,r));
		return ans;
	}
}

int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	TREE *root=new TREE;
	scanf("%d",&n);
	for (int i=1;i<=n+1;++i)
	 scanf("%d",&a[i]);
	build(root,1,n+2);
	scanf("%d",&m);
	int x,y;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		ans=-0x7f;
		if (x==y) printf("%d\n",a[x+1]);
		else
		 printf("%d\n",Q(root,x+1,y+2));
	}
}