记录编号	117995	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	182.[USACO Jan07] 均衡队形	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.272 s
提交时间	2014-09-03 11:50:30	内存使用	30.81 MiB

#include<cstdio>
#include<cctype>
#define MAXN 1000010
using namespace std;
int N=0,M=1,Q=0;
int T[MAXN<<2]={0},V[MAXN<<2]={0};

int MAX(int x,int y){
	if(x>y)	return x;
	return y;
} 

int MIN(int x,int y){
	if(x<y)	return x;
	return y;
}

inline int getint(){
	char ch;
	int x = 0;
	while (!isdigit(ch = getchar()));
	x = ch - 48;
	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
	return x;
}

int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	
	N=getint();
	Q=getint();
	for(M=1;M<N+2;M<<=1);
	
	for(int i=1;i<=N;++i){
		T[i+M]=getint();
		V[i+M]=T[i+M];
	}
	
	for(int i=M-1;i>=1;--i){
		T[i]=MAX(T[i<<1],T[(i<<1)+1]);
		V[i]=MIN(V[i<<1],V[(i<<1)+1]);	
	}
	
	int a,b;
	for(int i=1;i<=Q;++i){
		a=getint();
		b=getint();
		int s=a+M-1,t=b+M+1;
		int Lans=0,Rans=999999;
		for(;s^t^1;s>>=1,t>>=1){
			if(!(s&1))	Lans=MAX(Lans,T[s^1]),Rans=MIN(Rans,V[s^1]);
			if( (t&1))	Lans=MAX(Lans,T[t^1]),Rans=MIN(Rans,V[t^1]);
		}
		
		printf("%d\n",Lans-Rans);
	}
	return 0;
}