poj 3264 Balanced Lineup(线段树)

#include <limits>
#include <cstdio>
#include <iostream>
using namespace std;

const int MAX_N = 200000;
const int N_VAL = 50000 + 10;
struct SegTreeNode
{
    int valMin, valMax;
};

SegTreeNode segTree[MAX_N];
int val[N_VAL];
int valMax, valMin;

int Max(int a, int b) { return a > b ? a : b; }
int Min(int a, int b) { return a > b ? b : a; }
void Build(int root, int nbegin, int nend, int arr[])
{
    if (nbegin == nend)
    {
        segTree[root].valMax = arr[nbegin];
        segTree[root].valMin = arr[nbegin];
    }
    else
    {
        int mid = (nbegin + nend) / 2;

        Build(2 * root, nbegin, mid, arr);
        Build(2 * root + 1, mid + 1, nend, arr);
        segTree[root].valMax = Max(segTree[2 * root].valMax, segTree[2 * root + 1].valMax);
        segTree[root].valMin = Min(segTree[2 * root].valMin, segTree[2 * root + 1].valMin);
    }
}

void Query(int root, int nbegin, int nend, int qbegin, int qend)
{
    if (nbegin > qend || nend < qbegin)
        return;
    if (qbegin <= nbegin && qend >= nend)
    {
        if (valMax < segTree[root].valMax)
            valMax = segTree[root].valMax;
        if (valMin > segTree[root].valMin)
            valMin = segTree[root].valMin;
        return;
    }

    int mid = (nbegin + nend) / 2;
    
    Query(2 * root, nbegin, mid, qbegin, qend);
    Query(2 * root + 1, mid + 1, nend, qbegin, qend);
}

int main()
{
    int qbegin, qend;
    int count = 0, N, Q;

    scanf("%d%d", &N, &Q);
    while (count++ < N)
        scanf("%d", &val[count]);

    Build(1, 1, N, val);
    while (Q--)
    {
        valMax = INT_MIN, valMin = INT_MAX;
        scanf("%d%d", &qbegin, &qend);
        Query(1, 1, N, qbegin, qend);
        printf("%d\n", valMax - valMin);
    }

    return 0;
}