记录编号	45994	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	Cloud	是否通过	通过
代码语言	C++	运行时间	1.976 s
提交时间	2012-10-26 10:02:19	内存使用	55.08 MiB

#include<fstream>
#include<cmath>
using namespace std;
int max(int x,int y)
{
	if(x>y)
		return x;
	else
		return y;
}
int min(int x,int y)
{
	if(x<y)
		return x;
	else
		return y;
}
int a[500001];
int mx[500001][16],mn[500001][16];
int m;
int main(void)
{
	ifstream fin("lineup.in");
	ofstream fout("lineup.out");
	int n,q;
	int i,j,k;
	fin>>n>>q;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
		mx[i][0]=a[i];
		mn[i][0]=a[i];
	}
	m=floor(log((double)n)/log(2.0));
	for(j=1;j<=m;j++)
		for(i=n;i>0;i--)
		{
			mx[i][j]=mx[i][j-1];
			if(i+(1<<(j-1))<=n)
				mx[i][j]=max(mx[i][j],mx[i+(1<<(j-1))][j-1]);
		}
	for(j=1;j<=m;j++)
		for(i=n;i>0;i--)
			if(i+(1<<(j-1))<=n)
			{
				mn[i][j]=mn[i][j-1];
				mn[i][j]=min(mn[i][j],mn[i+(1<<(j-1))][j-1]);
			}
	int x,y;
	for(k=0;k<q;k++)
	{
		fin>>i>>j;
		m=floor(log((double)(j-i+1))/log(2.0));
		x=max(mx[i][m],mx[j-(1<<m)+1][m]);
		y=min(mn[i][m],mn[j-(1<<m)+1][m]);
		fout<<x-y<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}