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

題目大意

N ≤ 200000 個學生，初始分數給定。M < 50000 個操作：

• Q A B：查詢區間 [A,B] 最大分數。
• U A B：將學生 A 分數改為 B。

多測試用例，直到 EOF。

線段樹結構

void build(int rt, int l, int r) {
    tree[rt].l = l; tree[rt].r = r;
    if (l == r) { tree[rt].maxv = score[l]; return; }
    int mid = (l+r)/2;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
    tree[rt].maxv = max(tree[rt<<1].maxv, tree[rt<<1|1].maxv);
}

單點更新

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

主程序

關鍵優化

使用 scanf 而非 cin（大數據量下快得多）。
線段樹陣列大小開 4*N（此處 800000 足夠）。
遞歸深度 log2(200000) ≈ 18，棧安全。
查詢函數利用節點區間完全匹配優化，減少遞歸分支。


複雜度
建樹 O(N)，單次更新/查詢 O(log N)。總操作 (N+M) log N ≈ 250000 × 18 ≈ 4.5e6，極快。

常見錯誤

未處理多測試用例之間的全局變量清理（陣列覆蓋重建即可）。
scanf(" %c") 前加空格跳過換行符。
區間端點包含關係：題目 [A,B] 閉區間，代碼一致。