QWQ，献上蒟蒻的代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define lowbit(x) x&-x
#define M 50005


using namespace std;
inline int read(){
	int x=0;int f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();	}
	return x*f;
}

int n,m;
int a[M],h_Mx[M],h_Mi[M];
inline void Mx_update(int x,int w){
	for(h_Mx[x]=w;x<=n;x+=lowbit(x))
		for(int i=1;i<lowbit(x);i<<=1)
			h_Mx[x]=max(h_Mx[x],h_Mx[x-i]);
}
inline int Mx_qurry(int x,int y){
	int res=0;
	while(y>=x){
		res=max(res,a[y]);
		for(y=y-1;y-lowbit(y)>=x;y-=lowbit(y))
		res=max(res,h_Mx[y]);
	}
	return res;
}
inline void Mi_update(int x,int w){
	for(h_Mi[x]=w;x<=n;x+=lowbit(x))
		for(int i=1;i<lowbit(x);i<<=1)
			h_Mi[x]=min(h_Mi[x],h_Mi[x-i]);
}
inline int Mi_qurry(int x,int y){
	int res=inf;
	while(y>=x){
		res=min(res,a[y]);
		for(y=y-1;y-lowbit(y)>=x;y-=lowbit(y))
		res=min(res,h_Mi[y]);
	}
	return res;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)
		h_Mx[i]=0,h_Mi[i]=0;
	for(int i=1;i<=n;++i){
		a[i]=read();
		Mx_update(i,a[i]);
		Mi_update(i,a[i]);
	}
	while(m--){
		int x=read(),y=read();
		int mx=Mx_qurry(x,y);
		int mi=Mi_qurry(x,y);
		printf("%d\n",mx-mi);
	}		
	return 0;
}