记录编号	394862	评测结果	AWWWWWWWWWWWWWWWWA
题目名称	[USACO Jan07] 均衡队形	最终得分	11
用户昵称	TARDIS	是否通过	未通过
代码语言	C++	运行时间	7.607 s
提交时间	2017-04-14 18:42:01	内存使用	0.54 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#include<deque>
#define itn int
#define coder goodboy
using namespace std;
typedef long long LL;typedef unsigned long long ULL;
const int maxn=50010;
int a[maxn],bmin[maxn],bmax[maxn],n,m,b,temp1,temp2,ans1,ans2;
inline void in(){
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	scanf("%d%d",&n,&m);b=floor(sqrt(n+1));
	for (int i=1;i<=n;i++){
		bmin[i]=1000010,bmax[i]=-1;
	}
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		bmin[i/b]=min(bmin[i/b],a[i]);
		bmax[i/b]=max(bmax[i/b],a[i]);
	}
}
inline void regular(int l,int r,int &Min,int &Max){
	for (int i=l;i<=r;i++){
		Min=min(Min,a[i]);
		Max=max(Max,a[i]);
	}
}
inline void get(int L,int R,int &Min,int &Max){
	for (int i=L;i<=R;i++){
		Min=min(Min,bmin[i]);
		Max=max(Max,bmax[i]);
	}
}
inline void query(int l,int r,int &Min,int &Max){
	Min=1000010;Max=-1;
	int L=l/b,R=r/b;
	if (l%b){
		if (R-L>2){
			regular(l,r,Min,Max);
			return;
		}
		else{
			regular(l,(L+1)*b,Min,Max);
			if (r%b) regular(R*b,r,Min,Max);
			get(L+1,R,Min,Max);
		}
	}
	else{
		if (R-L<1){
			regular(l,r,Min,Max);
			return;
		}
		else{
			if (r%b) regular(R*b,r,Min,Max);
			get(L,R,Min,Max);
		}
	}
	return;
}
int Main(){
	in();
	for (int i=1;i<=m;i++){
		scanf("%d%d",&temp1,&temp2);
		query(temp1,temp2,ans1,ans2);
		printf("%d\n",ans2-ans1);
	}
	return 0;
}
int main(){;}
int goodboy=Main();