记录编号	57208	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.589 s
提交时间	2013-04-07 16:02:43	内存使用	10.75 MiB

#include<iostream>
#include<cstdio>
#include<deque>
#include<algorithm>
#include<vector>
using namespace std;
const long long SIZEN=50001,SIZEQ=200001;;
long long INF=1000010;
class NODE{
public:
	long long left,right;
	long long lchild,rchild;
	long long max,min;
}tree[4*SIZEN+1];
long long tot=0;
long long d[SIZEN]={0};
long long l[SIZEQ]={0},r[SIZEQ]={0};//询问的区间
//节点下标是1~n
long long n,q;//n个牛,q个询问
long long max(long long a,long long b){
	return (a>b)?a:b;
}
long long min(long long a,long long b){
	return (a<b)?a:b;
}
void maketree(long long root,long long left,long long right){
	tree[root].left=left,tree[root].right=right;
	if(left<right){
		long long mid=(left+right)/2;
		tree[root].lchild=++tot;
		maketree(tot,left,mid);
		tree[root].rchild=++tot;
		maketree(tot,mid+1,right);
		tree[root].max=max(tree[tree[root].lchild].max,tree[tree[root].rchild].max);
		tree[root].min=min(tree[tree[root].lchild].min,tree[tree[root].rchild].min);
	}
	else{
		tree[root].max=tree[root].min=d[left];
		tree[root].lchild=tree[root].rchild=-1;
	}
}
long long getmax(long long root,long long left,long long right){
	if(root==-1||left>tree[root].right||right<tree[root].left) return 0;//不包含
	if(tree[root].left>=left&&tree[root].right<=right) return tree[root].max;
	else return max(getmax(tree[root].lchild,left,right),getmax(tree[root].rchild,left,right));
}
long long getmin(long long root,long long left,long long right){
	if(root==-1||left>tree[root].right||right<tree[root].left) return INF;//不包含
	if(tree[root].left>=left&&tree[root].right<=right) return tree[root].min;
	else return min(getmin(tree[root].lchild,left,right),getmin(tree[root].rchild,left,right));
}
void read(void){
	scanf("%d%d",&n,&q);
	long long i;
	for(i=1;i<=n;i++) scanf("%d",&d[i]);
	for(i=1;i<=q;i++) scanf("%d%d",&l[i],&r[i]);
}
void work(void){
	long long lnow,rnow;
	long long maxnow,minnow;
	long long temp;
	long long i;
	for(i=1;i<=q;i++){
		lnow=l[i],rnow=r[i];
		maxnow=getmax(0,lnow,rnow);
		minnow=getmin(0,lnow,rnow);
		temp=maxnow-minnow;
		printf("%d\n",temp);
	}
}
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	read();
	maketree(tot,1,n);
	work();
	return 0;
}