P2880 [USACO07JAN] Balanced Lineup G

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int treex[maxn*4],treen[maxn*4],a[maxn],n,m,l,r,ans1,ans2;
void build(int l=1,int r=n,int p=1){
	if(l==r){
		treex[p]=a[l];
		treen[p]=a[l];
	}
	else{
		int mid=(l+r)/2;
		build(l,mid,p*2);
		build(mid+1,r,p*2+1);
		treex[p]=max(treex[p*2],treex[p*2+1]);
		treen[p]=min(treen[p*2],treen[p*2+1]);
	}
}
int query(int l,int r,int p=1,int cl=1,int cr=n){
	if(cl>=l&&cr<=r){
		ans1=max(ans1,treex[p]);
		ans2=min(ans2,treen[p]);
	}
	else{
		int mid=(cl+cr)/2;
		if(l<=mid){
			query(l,r,p*2,cl,mid);
		}
		else{
			query(l,r,p*2+1,mid+1,cr);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build();
	while(m--){
		ans1=-1e9;
		ans2=1e9;
		cin>>l>>r;
		query(l,r);
		cout<<abs(ans1-ans2)<<endl;
	}
	return 0;
}