记录编号	166849	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	2.879 s
提交时间	2015-06-16 14:42:32	内存使用	36.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define SpeedUp ios::sync_with_stdio(false)
using namespace std;
struct TREE{
	int sum1,sum2;
	int l;
	int r;
	TREE *lc,*rc;
	TREE():sum1(0),sum2(0){}
};
int n,m;
int ans;
int a[10000000];

void build (TREE *p,int l,int r)
{
	p->l=l;
	p->r=r;
	if (l+1==r)
	 p->sum1=p->sum2=a[l];
	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->sum1=max(p->lc->sum1,p->rc->sum1);
		p->sum2=min(p->lc->sum2,p->rc->sum2);
	}
}

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

int Q2(TREE *p,int l,int r){
	if (l<=p->l&&p->r<=r) return ans=min(ans,p->sum2);
	else
	{
		if (l<(p->l+p->r)/2)
			ans=min(Q2(p->lc,l,r),ans);
		if (r>(p->l+p->r)/2)
			ans=min(Q2(p->rc,l,r),ans);
		return ans;
	}
}
int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	cin>>n>>m;
	for (int i=1;i<=n;++i)
	 cin>>a[i];
	TREE *root=new TREE;
	build(root,1,n+1);
	int x,y;	
	for (int i=1;i<=m;++i)
	{
	    ans=-0x7f;
		cin>>x>>y;
		int A1=Q1(root,x,y+1);
		ans=200000000;
		int A2=Q2(root,x,y+1);
		cout<<A1-A2<<endl;
	}
}