自己感觉是 $O(n\log n)$ 的。

#include<bits/stdc++.h>
using namespace std;
long long n,q,t[50005],t2[50005],a[50005],x,y;
long long lowbit(long long x)
{
    return x&-x;
}
void update(long long x,long long k)
{
    while(x<=n)
    {
        if(k>t[x])t[x]=k;
        if(k<t2[x])t2[x]=k;
        x+=lowbit(x);
    }
}
long long getmx(long long x,long long y)
{
    long long mx=0;
    while(x<=y)
    {
    	if(y-lowbit(y)+1<x)
    	{
    		if(a[y]>mx)mx=a[y];
    		y--; 
		}
        else
		{
			if(t[y]>mx)mx=t[y]; 
			y-=lowbit(y);
		}
    }
    return mx;
}
long long getmn(long long x,long long y)
{
    long long mn=1e18;
    while(x<=y)
    {	
    	if(y-lowbit(y)+1<x)
    	{
    		if(a[y]<mn)mn=a[y];
    		y--; 
		}
        else
		{
			if(t2[y]<mn)mn=t2[y]; 
			y-=lowbit(y);
		}
    }
    return mn;
}
int main()
{
	memset(t2,127,sizeof(t2));
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		update(i,a[i]);	
	}
	while(q--)
	{
		cin>>x>>y;
		cout<<getmx(x,y)-getmn(x,y)<<endl;
	}
}