记录编号	122015	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.989 s
提交时间	2014-09-22 12:53:13	内存使用	30.83 MiB

#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define Maxn 200003
using namespace std;
int n,m,mi[Maxn][20]={0},ma[Maxn][20]={0};
int RMQ(int x,int y,bool a){
	if(x>y) swap(x,y);
	int k=0;
	while((1<<(k+1))<=y-x+1) k++;
	if(a) return min(mi[x][k],mi[y-(1<<k)+1][k]);
	else return max(ma[x][k],ma[y-(1<<k)+1][k]);
}
void init(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>mi[i][0];
		ma[i][0]=mi[i][0];
	}
	for(int i=1;(1<<i)<=n;i++)
	{
		for(int j=1;j+(1<<i)-1<=n;j++)
		{
			mi[j][i]=min(mi[j][i-1],mi[j+(1<<(i-1))][i-1]);
			ma[j][i]=max(ma[j][i-1],ma[j+(1<<(i-1))][i-1]);
		}
	}
	int x,y;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		cout<<RMQ(x,y,false)-RMQ(x,y,true)<<endl;
	}
}
int main(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	init();
	return 0;
}