POJ 3264 Balanced Lineup：線段樹維護區間最值差

題目描述

農夫約翰有 N (≤ 50,000) 隻奶牛按固定順序排隊。他有 Q (≤ 200,000) 個詢問，每個詢問給出區間 [A, B]，要求輸出該區間內最高與最矮奶牛的身高差。身高範圍 1~1,000,000。

解法：線段樹維護區間最小值與最大值

經典的區間最值查詢問題。線段樹每個節點存儲該區間的 Min 與 Max。查詢時合併左右子區間的最值，最終得到整個查詢區間的最值，相減即為答案。

線段樹結構

struct Node { int Min, Max; } tree[4 * MAXN];
int height[MAXN];

建樹

void build(int node, int l, int r) {
    if (l == r) {
        tree[node].Min = tree[node].Max = height[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(node<<1, l, mid);
    build(node<<1|1, mid+1, r);
    tree[node].Min = min(tree[node<<1].Min, tree[node<<1|1].Min);
    tree[node].Max = max(tree[node<<1].Max, tree[node<<1|1].Max);
}

查詢

// flag=0 查最小值，flag=1 查最大值
int query(int node, int l, int r, int ql, int qr, int flag) {
    if (qr < l || r < ql) return flag ? -1 : INF;
    if (ql <= l && r <= qr) return flag ? tree[node].Max : tree[node].Min;
    int mid = (l + r) >> 1;
    int left = query(node<<1, l, mid, ql, qr, flag);
    int right = query(node<<1|1, mid+1, r, ql, qr, flag);
    return flag ? max(left, right) : min(left, right);
}

主程式

int main() {
    int n, q;
    while (~scanf("%d%d", &n, &q)) {
        for (int i = 1; i <= n; ++i) scanf("%d", &height[i]);
        build(1, 1, n);
        while (q--) {
            int a, b; scanf("%d%d", &a, &b);
            int mx = query(1, 1, n, a, b, 1);
            int mn = query(1, 1, n, a, b, 0);
            printf("%d\n", mx - mn);
        }
    }
    return 0;
}

複雜度分析

• 建樹：O(N)
• 單次查詢：O(log N)
• 總時間：O(N + Q log N) ≈ 50,000 + 200,000 × 16 ≈ 3.2×10⁶ 操作，極快。
• 空間：O(4N) ≈ 200,000 節點。

優化提示

• 可將兩次查詢合併為一次，返回 pair<min, max>，減少常數因子。
• 輸入量大，建議用 scanf/printf 或快速 IO。
• 也可用 Sparse Table (ST) 算法，預處理 O(N log N)，查詢 O(1)，但記憶體較大；線段樹更通用、易修改。

總結

POJ 3264 是線段樹維護區間最值的入門經典題。掌握「節點存什麼、怎麼合併、怎麼查詢」三步曲，即可輕鬆解決大多數區間最值/求和/區間最值差問題。