PKU 3264 : Balanced Lineup

セグメント木の典型問題.
Range (Minimum | Maximum) Queryの問題です.
本当は1ついらない関数があります. 面倒なので2つ書きましたが.

#include <stdio.h>

#define INF (1 << 30)
#define MAX_N (1 << 16)
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))

int segMin[2 * MAX_N], segMax[2 * MAX_N];
int seg_size;

void init(int size){
    int i;
    seg_size = 1;
    
    while (seg_size < size){
        seg_size *= 2;
    }
    
    for (i = 0; i < seg_size; i++){
        segMin[i] = INF;
        segMax[i] = -INF;
    }
}

void update(int k, int x)
{
    k += seg_size - 1;
    segMin[k] = segMax[k] = x;
    
    while (k != 0){
        k = (k - 1) / 2;
        segMin[k] = min(segMin[k * 2 + 1], segMin[k * 2 + 2]);
        segMax[k] = max(segMax[k * 2 + 1], segMax[k * 2 + 2]);
    }
}

int queryMin(int a, int b, int k, int l, int r)
{
    int vl, vr;
    
    if (r <= a || b <= l){
        return (INF);
    }
    
    if (a <= l && r <= b){
        return (segMin[k]);
    }
    else {
        vl = queryMin(a, b, k * 2 + 1, l, (l + r) / 2);
        vr = queryMin(a, b, k * 2 + 2, (l + r) / 2, r);
    }
    return (min(vl, vr));
}

int queryMax(int a, int b, int k, int l, int r)
{
    int vl, vr;
    
    if (r <= a || b <= l){
        return (-INF);
    }
    
    if (a <= l && r <= b){
        return (segMax[k]);
    }
    else {
        vl = queryMax(a, b, k * 2 + 1, l, (l + r) / 2);
        vr = queryMax(a, b, k * 2 + 2, (l + r) / 2, r);
    }
    return (max(vl, vr));
}

int main(void)
{
    int N, Q;
    int i;
    int data;
    int left, right;
    
    scanf("%d%d", &N, &Q);
    
    init(N);
    
    for (i = 0; i < N; i++){
        scanf("%d", &data);
        update(i, data);
    }
    
    for (i = 0; i < Q; i++){
        scanf("%d%d", &left, &right);
        printf("%d\n", queryMax(--left, right, 0, 0, seg_size) - queryMin(left, right, 0, 0, seg_size));
    }
    
    return (0);
}