分块36pts求条（关）

#include<bits/stdc++.h>
using namespace std;
int n,q,bl,t;
int cnt[50001],tail[300],head[300],a[50001],mx[300],mn[300];
int main(){
	cin>>n>>q;
	bl=sqrt(n);
	t=n/bl;
	memset(mn,0x3f3f3f3f,sizeof(mn));
	for(int i=1;i<=n;++i){
		cin>>a[i];
		cnt[i]=(i-1)/bl+1;
		mn[cnt[i]]=min(mn[cnt[i]],a[i]);
		mx[cnt[i]]=max(mx[cnt[i]],a[i]);
	}
	for(int i=1;i<=t;++i){
		head[i]=(i-1)*bl+1;
		tail[i]=i*bl;
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		int l=0,s=0x3f3f3f3f;
		if(cnt[x]==cnt[y])
			for(int i=x;i<=y;++i)
				l=max(l,a[i]),s=min(s,a[i]);
		else if(cnt[x]+1==cnt[y]){
			for(int i=x;i<=tail[cnt[x]];++i)
				l=max(l,a[i]),s=min(s,a[i]);
			for(int i=head[cnt[y]];i<=y;++i)
				l=max(l,a[i]),s=min(s,a[i]);
		}
		else{
			for(int i=cnt[x]+1;i<=cnt[y]-1;++i)
				l=max(l,mx[i]),s=min(s,mn[i]);
			for(int i=x;i<=tail[cnt[x]];++i)
				l=max(l,a[i]),s=min(s,a[i]);
			for(int i=head[cnt[y]];i<=y;++i)
				l=max(l,a[i]),s=min(s,a[i]);
		}
		cout<<l-s<<'\n';
	}
	return 0;
}