代码

#include <bits/stdc++.h>
using namespace std;
#define M 100086
int n, q, h[M], log_2[M], rmax[M][18], rmin[M][18];
int ST()
{
    for (int i = 1; i <= n; i++)
        rmax[i][0] = rmin[i][0] = h[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            rmax[i][j] = max(rmax[i][j - 1], rmax[i + (1 << (j - 1))][j - 1]);
            rmin[i][j] = min(rmin[i][j - 1], rmin[i + (1 << (j - 1))][j - 1]);
        }
}
int query_max(int A, int B)
{
    int x = log_2[B - A + 1];
    return max(rmax[A][x], rmax[B - (1 << x) + 1][x]);
}
int query_min(int A, int B)
{
    int x = log_2[B - A + 1];
    return min(rmin[A][x], rmin[B - (1 << x) + 1][x]);
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    for (int k = 2; k <= n; k++)
        log_2[k] = log_2[k / 2] + 1;
    ST();
    while (q--)
    {
        int A, B;
        scanf("%d%d", &A, &B);
        printf("%d\n", (query_max(A, B) - query_min(A, B)));
    }
    return 0;
}