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;
}