记录编号	159885	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.039 s
提交时间	2015-04-22 22:16:44	内存使用	0.51 MiB

#include<cstdio>
#include<iostream>
using namespace std;
#define Nil NULL
int n,Q,maxn=0xffffff,b[50010];
class Node
{
public:
	int l,r;
	Node *lc,*rc;
	int high,low;
	Node()
	{
		l=r=0;
		lc=rc=Nil;
		low=maxn;
		high=0;
	}
	void push_up(void)
	{
		if(lc!=Nil)
		{
			high=max(lc->high,rc->high);
			low=min(lc->low,rc->low);
	    }
	}
	int miku (int x,int y,bool t)
	{
		if(x>r||y<l)
		{
			if(t==1) return maxn;
			if(t==0) return 0;
		}
		if(l>=x&&r<=y)
		{
			if(t==1) return low;
			else return high;
		}
		else
		{
			if(t==1) return min(lc->miku(x,y,t),rc->miku(x,y,t));
			else return max(lc->miku(x,y,t),rc->miku(x,y,t));
		}
	}//0求high，1求low
};
Node* build(int a[],int x,int y)
{
	Node *p=new Node;
	p->l=x;p->r=y;
	if(x==y)
	{
		p->high=a[x];
		p->low=a[x];
	}
	else{int mid=(x+y)/2;
	p->lc=build(a,x,mid);
	p->rc=build(a,mid+1,y);
	p->push_up();	
	}
	return p;
}
Node *root;
int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	root=build(b,1,n);
	for(int i=1;i<=Q;i++)
	{
		int A,B;
		scanf("%d%d",&A,&B);
		printf("%d\n",root->miku(A,B,0)-root->miku(A,B,1));
	}
	return 0;
}