记录编号	225561	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.715 s
提交时间	2016-02-17 14:26:58	内存使用	1.82 MiB

#include<cstdio>
#include<cstring>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
const int maxn=50010<<2;
int a[maxn]={0},b[maxn];
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
void build(int,int,int);
int qerymax(int,int,int,int,int);
int qerymin(int,int,int,int,int);
int n,m,s,t;
int main(){
#define COGS
#ifdef COGS
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
#endif
	memset(b,127,sizeof(b));
	scanf("%d%d",&n,&m);
	build(1,n,1);
	for(int i=0;i<m;i++){
		scanf("%d%d",&s,&t);
		printf("%d\n",qerymax(s,t,1,n,1)-qerymin(s,t,1,n,1));
	}
#ifdef COGS
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}
void build(int l,int r,int rt){
	if(l==r){
		scanf("%d",&a[rt]);
		b[rt]=a[rt];
		return;
	}
	int mid=(l+r)/2;
	build(lch);
	build(rch);
	a[rt]=max(a[rt<<1],a[rt<<1|1]);
	b[rt]=min(b[rt<<1],b[rt<<1|1]);
}
int qerymax(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	int mid=(l+r)/2;
	if(t<=mid)return qerymax(s,t,lch);
	if(s>mid)return qerymax(s,t,rch);
	return max(qerymax(s,t,lch),qerymax(s,t,rch));
}
int qerymin(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return b[rt];
	int mid=(l+r)/2;
	if(t<=mid)return qerymin(s,t,lch);
	if(s>mid)return qerymin(s,t,rch);
	return min(qerymin(s,t,lch),qerymin(s,t,rch));
}