最直观的朴素做法：遍历每一个区间找最大最小值，但是该方法会超时，无法通过。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10, M = 2e5;

int n, q;
int cow[N];
vector<PII> query;

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++ ) cin >> cow[i];
    for (int i = 1; i <= q; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});            //用vector来存区间
    }

    int k = 0;
    while (k < q)
    {
        int maxv = 0, minv = 1e6;           //遍历每个区间找最大最小值
        for (int i = query[k].first; i <= query[k].second; i ++ )
        {
            if (cow[i] > maxv) maxv = cow[i];
            if (cow[i] < minv) minv = cow[i];
        }

        cout << maxv - minv << endl;        //输出结果

        k ++ ;
    }

    return 0;
}

本题正解应该用ST表，是一个ST表模板题。

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5e4 + 10, M = 16;

int n, Q;
int h[N];
int f[N][M], g[N][M];                   //开两个ST表，f表示最大值，g表示最小值
int log[N];

int main()
{
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);

    for (int i = 1; i <= n; i ++ )      //枚举法预处理log，且向下取整
        while (1 << log[i] + 1 <= i)
            log[i] ++ ;

    for (int j = 0; 1 << j <= n; j ++ )         //预处理ST表
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j) f[i][j] = g[i][j] = h[i];   //f[i][0]的最大值就是h[i]
            else
            {
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
                g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
            }

    while (Q -- )                               //处理询问
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int t = log[r - l + 1];
        int maxh = max(f[l][t], f[r - (1 << t) + 1][t]);
        int minh = min(g[l][t], g[r - (1 << t) + 1][t]);

        printf("%d\n", maxh - minh);
    }

    return 0;    
}