ST表模板

```cpp

#include<cstdio>

#include<iostream>

using namespace std;

int f[100005][50],g[100005][50],LOG2[100005],POW2[100005],p;

int query(int l,int r)

{

    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()

{

    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;

    int i,j;

    for(i=2;i<=n;i++)

    {

        LOG2[i]=LOG2[i/2]+1;

    }

    POW2[0]=1;

    for(i=1;i<=LOG2[n];i++)

    {

        POW2[i]=POW2[i-1]*2;

    }

    for(j=1;j<=LOG2[n];j++)

    {

        for(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(i=1;i<=q;i++)

    {

        x,y;

        scanf("%d%d",&x,&y);

        printf("%d\n",query(x,y));

    }

    return 0;

}

```