题目链接：

https://www.luogu.org/problemnew/show/P2880

分析：

ST表实现即可，一个最大值数组和最小值数组同时维护

代码：

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
int LOG2[50005],POW2[50005],f[50005][30],g[50005][30];
int query(int l,int r)
{
    int p=LOG2[r-l+1];
    return (max(f[l][p],f[r-POW2[p]+1][p])-min(g[l][p],g[r-POW2[p]+1][p]));
}
int main()
{
//  cout<<log2(50000)<<endl;
    int n,q,a;
    scanf("%d%d",&n,&q); 
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        f[i][0]=a;
        g[i][0]=a;
    }
    LOG2[1]=0;
    for(int i=2;i<=n;i++)
    {
        LOG2[i]=LOG2[i/2]+1;
    }
    POW2[0]=1;
    for(int i=1;i<=LOG2[n];i++)
    {
        POW2[i]=POW2[i-1]*2; 
    }
    for(int j=1;j<=LOG2[n];j++)
    {
        for(int i=1;(i+POW2[j-1])<=n;i++)
        {
            f[i][j]=max(f[i][j-1],f[i+POW2[j-1]][j-1]);
            g[i][j]=min(g[i][j-1],g[i+POW2[j-1]][j-1]);
        }
    }
    int x,y;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y));
    }
    return 0;
}