记录编号	9671	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	1.697 s
提交时间	2009-04-10 21:02:39	内存使用	4.08 MiB

/* 
 * Problem: 延绵的山峰 climb
 * Author: Guo Jiabao
 * Time: 2009.4.10 21:01
 * State: 
 * Memo: Segment Tree
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#define MAXN 1000001
using namespace std;
int S[MAXN];
struct node
{
	node *left,*right;
	int a,b;
	int v;
	node(int ta,int tb)
	{
		a=ta;b=tb;
		left=right=0;
	}
};
struct segmenttree
{
	int size;
	node *root;
	inline int max(int a,int b){return a>b?a:b;}
	void create(node *N,int A,int B)
	{
		if (A==B)
		{
			N->v=S[A];
			return;
		}
		int M=(A+B)/2;
		N->left=new node(A,M);
		create(N->left,A,M);
		N->right=new node(M+1,B);
		create(N->right,M+1,B);
		N->v=max(N->left->v,N->right->v);
	}
	segmenttree(int n)
	{
		size=n;
		root=new node(0,size);
		create(root,0,size);
	}
	int _get(node *N,int a,int b)
	{
		if (a==N->a && b==N->b)
			return N->v;
		int M=(N->a+N->b)/2;
		if (b<=M)return _get(N->left,a,b);
		if (a>=M+1)return _get(N->right,a,b);
		int V1,V2;
		V1=_get(N->left,a,M);
		V2=_get(N->right,M+1,b);
		return max(V1,V2);
	}
	int get(int a,int b)
	{
		return _get(root,a,b);
	}
};
segmenttree *T;
int N;
void init()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int i;
	scanf("%d",&N);
	for (i=0;i<=N;i++)
		scanf("%d",&S[i]);
	T=new segmenttree(N);
}
void answer()
{
	int i,Q,a,b,v;
	scanf("%d",&Q);
	for (i=1;i<=Q;i++)
	{
		scanf("%d%d",&a,&b);
		v=T->get(a,b);
		printf("%d\n",v);
	}
}
int main()
{
	init();
	answer();
	return 0;
}