POJ3264
ST模板题，区间最大值 - 区间最小值

//#include <bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;

const int maxn = 50050;
int Max[maxn][20], Min[maxn][20];
int H[maxn];
int N, Q;

void ST_Create(){
    for(int i = 1; i <= N; i++)
        Max[i][0] = Min[i][0] = H[i];
    int k = log2(N);
    for(int j = 1; j <= k; j++)
        for(int i = 1; i <= N - (1<<j) + 1; i++){
            Max[i][j] = max(Max[i][j-1], Max[i+(1<<(j-1))][j-1]);
            Min[i][j] = min(Min[i][j-1], Min[i+(1<<(j-1))][j-1]);
        }
}

int ST_query(int l, int r){
    int k = log2(r - l + 1);
    int MaxN = max(Max[l][k], Max[r-(1<<k)+1][k]);
    int MinN = min(Min[l][k], Min[r-(1<<k)+1][k]);
    return MaxN - MinN;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d%d", &N, &Q);
    for(int i = 1; i <= N; i++)
        scanf("%d", &H[i]);
    ST_Create();
    while(Q--){
        int x,y;
        scanf("%d%d", &x, &y);
        printf("%d\n", ST_query(x, y));
    }
    return 0;
}

吐槽一下：都9012年了，还需要写这么多头文件