记录编号	166295	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.743 s
提交时间	2015-06-14 21:35:12	内存使用	3.36 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
inline int in()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return x;
}
int n,sum[400000],y,q,k,h,a[400000];
int MAX(int h,int hh)
{
	if(h>hh) return h;
	else
	 return hh;
}
int MIN(int h,int hh)
{
	if(h>hh) return hh;
	return h;
}
void build(int x,int y,int r)
{
	if(x==y)
	{
		a[r]=sum[r]=in();
		return;
	}
	int mid=(x+y)>>1;
	build(x,mid,r<<1);
	build(mid+1,y,(r<<1)+1);
	sum[r]=MAX(sum[r<<1],sum[(r<<1)+1]);
	a[r]=MIN(a[r<<1],a[(r<<1)+1]);
}
int wen(int x,int y,int r,int u,int l)
{   
	if(x<=r&&y>=u)
	{
		return sum[l];
	}
	int mid=(r+u)>>1;
	int maxn=0;
	if(x<=mid)
	  {
			maxn=MAX(maxn,wen(x,y,r,mid,l<<1));
	  }
	if(y>mid)
	  {
			maxn=MAX(maxn,wen(x,y,mid+1,u,(l<<1)+1));
	  }
	return maxn;
}
int wen1(int x,int y,int r,int u,int l)
{
	if(x<=r&&y>=u)
	{
		return a[l];
	}
	int mid=(r+u)>>1;
	int maxn=99999999;
	if(x<=mid)
	  {
			maxn=MIN(maxn,wen1(x,y,r,mid,l<<1));
	  }
	if(y>mid)
	  {
			maxn=MIN(maxn,wen1(x,y,mid+1,u,(l<<1)+1));
	  }
	return maxn;
}
int main()
{   freopen("lineup.in", "r", stdin);
    freopen("lineup.out", "w", stdout);
    n=in();
    y=in();
    build(1,n,1);
    for(int i=1;i<=y;++i)
    {
		scanf("%d%d",&k,&h);
		printf("%d\n",wen(k,h,1,n,1)-wen1(k,h,1,n,1));
    }
    //system("pause");
}