c++代码给定一个长度为n的数组，有m次问询，每次问[l, r]区间的最大值与最小值之间的差值。 输入 测试样例由多组测试数据组成。 每个样例包含两行：第一行输入两个正整数n和m； 第二行输入n个整数ai。 接下来m行，每行输入2个整数li, ri 1 <= n, m <= 105， 1 <= li <= ri <= n，-109 <= ai <= 109 输出 每个样例输出m行，每行包含一个整数，表示[l, r]区间的最大值与最小值的差。

下面是一个简单的解法，使用线段树维护区间最大值和最小值。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int MAXN = 1e5 + 5;

int a[MAXN];
int maxv[MAXN << 2], minv[MAXN << 2];

void build(int p, int l, int r) {
    if (l == r) {
        maxv[p] = minv[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
    minv[p] = min(minv[p << 1], minv[p << 1 | 1]);
}

int query_max(int p, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return maxv[p];
    int mid = (l + r) >> 1, ans = INT_MIN;
    if (ql <= mid) ans = max(ans, query_max(p << 1, l, mid, ql, qr));
    if (qr > mid) ans = max(ans, query_max(p << 1 | 1, mid + 1, r, ql, qr));
    return ans;
}

int query_min(int p, int l, int r, int ql, int qr) {
    if (ql <= l && qr >= r) return minv[p];
    int mid = (l + r) >> 1, ans = INT_MAX;
    if (ql <= mid) ans = min(ans, query_min(p << 1, l, mid, ql, qr));
    if (qr > mid) ans = min(ans, query_min(p << 1 | 1, mid + 1, r, ql, qr));
    return ans;
}

int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        build(1, 1, n);
        while (m--) {
            int l, r;
            cin >> l >> r;
            int maxv = query_max(1, 1, n, l, r);
            int minv = query_min(1, 1, n, l, r);
            cout << maxv - minv << endl;
        }
    }
    return 0;
}

时间复杂度为 $O(m\log n)$。