记录编号	227772	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	3.239 s
提交时间	2016-02-18 20:45:58	内存使用	68.43 MiB

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define Mem(arr,val) memset(arr,val,sizeof(arr));
using namespace std;
const int maxn=10050000;
int a[maxn],b[maxn];
void Build(int,int,int);
int Qerymin(int,int,int,int,int);	
int Qerymax(int,int,int,int,int);	
int Min(int x,int y)
{
	return x<y?x:y;
}
int Max(int x,int y)
{
	return x>y?x:y;
}
void Init();
int main()
{
	#define Read
	#ifdef Read
	   freopen("lineup.in","r",stdin);
	   freopen("lineup.out","w",stdout);
	#endif
	Init();
	return 0;
}
void Init()
{
	Mem(b,0);
	int n;int m;	
	scanf("%d",&n);scanf("%d",&m);
	Build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int s,t;
		scanf("%d%d",&s,&t);
		int kmin=Qerymin(s,t,1,1,n),kmax=Qerymax(s,t,1,1,n);;
		printf("%d\n",kmax-kmin);
	}
}
void Build(int rt,int l,int r)
{
	if(l==r)
	{
		scanf("%d",&a[rt]);
		b[rt]=a[rt];
		return;
	}
	int mid=(l+r)>>1;
	Build(lson);
	Build(rson);
	a[rt]=Min(a[rt<<1],a[rt<<1|1]);
	b[rt]=Max(b[rt<<1],b[rt<<1|1]);
}
int Qerymin(int s,int t,int rt,int l,int r)
{
	if(s<=l&& t>=r)return a[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return Qerymin(s,t,lson);
	if(s>mid)return Qerymin(s,t,rson);
	return Min(Qerymin(s,t,lson),Qerymin(s,t,rson));
}	
int Qerymax(int s,int t,int rt,int l,int r)
{
	if(s<=l&& t>=r)return b[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return Qerymax(s,t,lson);
	if(s>mid)return Qerymax(s,t,rson);
	return Max(Qerymax(s,t,lson),Qerymax(s,t,rson));
}