记录编号	445915	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	liuyu	是否通过	通过
代码语言	C++	运行时间	0.510 s
提交时间	2017-09-07 07:32:59	内存使用	2.60 MiB

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=50000*4;
int n,q,s[N],minv[N],maxv[N],minn,maxn,ans,a,b;

void build(int o,int l,int r){
	if(l==r)minv[o]=maxv[o]=s[l];
	else {
		int m=l+(r-l)/2;
		int lc=2*o,rc=2*o+1;
		build(o<<1,l,m);
		build((o<<1)+1,m+1,r);
		minv[o]=min(minv[lc],minv[rc]);
		maxv[o]=max(maxv[lc],maxv[rc]);
	}
}

void query(int o,int l,int r){
	if(a<=l&&b>=r){
		minn=min(minn,minv[o]);
		maxn=max(maxn,maxv[o]);
	}
	else{
		int m=l+(r-l)/2;
		if(a<=m)query(o<<1,l,m);
		if(b>m)query((o<<1)+1,m+1,r);
	}
}

void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&s[i]);
	build(1,1,n);
}

int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	init();
	while(q--){
		scanf("%d%d",&a,&b);
		minn=1e9;maxn=-1e9;
		query(1,1,n);
		printf("%d\n",maxn-minn);
	}
	return 0;
}