HDU 1754 I Hate It - 線段樹區間最大值查詢與單點更新

問題描述

有 N 名學生（N ≤ 200,000），初始成績已知。支援 M 次操作（M < 50,000）：

• Q A B：查詢區間 [A, B] 最大成績
• U A B：將學生 A 成績更新為 B

線段樹節點設計

每個節點存儲區間 [l, r] 的最大值 maxVal。

struct Node {
    int l, r;
    int maxVal;
} tree[MAXN * 4];

核心操作

建樹（初始化為 0，後續通過 update 填入初始值）

void build(int l, int r, int idx) {
    tree[idx].l = l; tree[idx].r = r;
    tree[idx].maxVal = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, idx << 1);
    build(mid + 1, r, idx << 1 | 1);
}

單點更新

void update(int pos, int val, int idx) {
    if (tree[idx].l == tree[idx].r) {
        tree[idx].maxVal = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (pos <= mid) update(pos, val, idx << 1);
    else update(pos, val, idx << 1 | 1);
    tree[idx].maxVal = max(tree[idx<<1].maxVal, tree[idx<<1|1].maxVal);
}

區間最大值查詢

int query(int L, int R, int idx) {
    if (tree[idx].l == L && tree[idx].r == R)
        return tree[idx].maxVal;
    int mid = (tree[idx].l + tree[idx].r) >> 1;
    if (R <= mid) return query(L, R, idx << 1);
    if (L > mid) return query(L, R, idx << 1 | 1);
    return max(query(L, mid, idx << 1), query(mid + 1, R, idx << 1 | 1));
}

完整主程序

#include 
#include 
#include 
using namespace std;

const int MAXN = 200010;
struct Node { int l, r, maxVal; } tree[MAXN * 4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        build(1, n, 1);
        for (int i = 1; i <= n; ++i) {
            int score; scanf("%d", &score);
            update(i, score, 1);
        }
        
        char op;
        for (int i = 0; i < m; ++i) {
            scanf(" %c%d%d", &op, &a, &b);
            if (op == 'U') update(a, b, 1);
            else if (op == 'Q') printf("%d\n", query(a, b, 1));
        }
    }
    return 0;
}

關鍵區別：與 HDU 1166 對比

優化提示

• 區間最大值查詢可用全局變數 ans 遞歸更新，避免返回值傳遞開銷
• 大規模輸入必須用 scanf，cin 會 TLE
• 線段樹大小開 4*N（800,000+）