记录编号	393676	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	0.445 s
提交时间	2017-04-11 20:47:12	内存使用	7.94 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=50001;
const int maxm=20;
int a[maxn][maxm],b[maxn][maxm],n,q,v,u;
void init()
{
	memcpy(b,a,sizeof(a));
    for(int j=1;(1<<j)<=n;j++)
	  for(int i=1;i+(1<<j)-1<=n;i++)
	  {
		a[i][j]=min(a[i+(1<<(j-1))][j-1],a[i][j-1]);
		b[i][j]=max(b[i+(1<<(j-1))][j-1],b[i][j-1]);
	  }
}
void query(int l,int r)
{
	int k=0,v,u;
	while((1<<(k+1))<=r-l+1) k++;
	v=max(b[l][k],b[r-(1<<k)+1][k]);
	u=min(a[l][k],a[r-(1<<k)+1][k]);
	printf("%d\n",v-u);
}
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",&a[i][0]);
	}
	init();
	for(int i=1;i<=q;i++)
	{
	  scanf("%d%d",&v,&u);
	  query(v,u);
	}
	return 0;
}