求调线段树36pts

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,h[50001],a,b,tree[500001],mx[50001],mn[50001];
void update(ll x){
	mx[x]=max(mx[x*2],mx[x*2+1]);
	mn[x]=min(mn[x*2],mn[x*2+1]);
}
void buildtree(ll x,ll l,ll r){
	if (l==r){
		mn[x]=mx[x]=h[l];
		return;
	}
	ll mid=(l+r)/2;
	buildtree(2*x,l,mid);
	buildtree(2*x+1,mid+1,r);
	update(x);
}
ll querymx(ll x,ll l,ll r,ll L,ll R){
	if (L<=l && r<=R) return mx[x];
	ll mid=(l+r)/2,ans=-1;
	if (L<=mid) ans=max(ans,querymx(x*2,l,mid,L,R));
	if (mid<R) ans=max(ans,querymx(x*2+1,mid+1,r,L,R));
	return ans;
}
ll querymn(ll x,ll l,ll r,ll L,ll R){
	if (L<=l && r<=R) return mn[x];
	ll mid=(l+r)/2,ans=1e8;
	if (L<=mid) ans=min(ans,querymn(x*2,l,mid,L,R));
	if (mid<R) ans=min(ans,querymn(x*2+1,mid+1,r,L,R));
	return ans;
}
int main(){
	cin>>n>>q;
	for (ll i=1;i<=n;i++) cin>>h[i];
	buildtree(1,1,n);
	while (q--){
		cin>>a>>b;
		cout<<querymx(1,1,n,a,b)-querymn(1,1,n,a,b)<<'\n';
	}
}