记录编号	426804	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.338 s
提交时间	2017-07-19 10:15:54	内存使用	4.12 MiB

#include<cstdio>
#include<cctype>
#include<algorithm>
#define mid ((l+r)>>1)
#define mid_b ((now->l+now->r)>>1)
const int maxn=1e6+5;
using namespace std;
struct stree
{
	int l,r;
	int mx;
	stree *ls,*rs;
	stree(){l=r=mx=0;ls=rs=NULL;}
}*root;
inline int get();
stree *build(int l,int r);
int search(stree *now,int l,int r);
int n,q;
int a,b;
int N[maxn];
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	n=get();get();
	for(int i=1;i<=n;i++)N[i]=get();
	root=build(0,n);
	q=get();
	for(int i=1;i<=q;i++)
	{
		a=get();b=get();
		printf("%d\n",search(root,a,b));
	}
	return 0;
}
int search(stree *now,int l,int r)
{
	if(now->l==l&&now->r==r)return now->mx;
	else if(r<=mid_b)return search(now->ls,l,r);
	else if(l>mid_b)return search(now->rs,l,r);
	else return max(search(now->ls,l,mid_b),search(now->rs,mid_b+1,r));
}
stree *build(int l,int r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)p->mx=N[l];
	else 
	{
		p->ls=build(l,mid);
		p->rs=build(mid+1,r);
		p->mx=max(p->ls->mx,p->rs->mx);
	}
	return p;
}
inline int get()
{
	int t=0,jud=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')jud=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return t*jud;
}