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

題目大意

維護 N (≤200,000) 名學生成績，支持 M (≤5,000) 次操作：
Q A B：查詢區間 [A,B] 最大分數
U A B：將第 A 名學生成績改為 B

線段樹結構

• 節點存儲區間最大值
• 構建：遞歸建樹，葉節點存初始分數，父節點取兩子最大值
• 更新：遞歸定位葉節點修改，回溯更新祖先最大值
• 查詢：標準區間最大值查詢，完全覆蓋直接返回，部分覆蓋分左右子樹查詢取最大

關鍵代碼

struct SegTree {
    vector<int> mx;
    int n;
    SegTree(int _n): n(_n), mx(4*_n) {}
    void build(int o, int l, int r, const vector<int>& a) {
        if (l == r) { mx[o] = a[l]; return; }
        int mid = (l+r)/2;
        build(o*2, l, mid, a);
        build(o*2+1, mid+1, r, a);
        mx[o] = max(mx[o*2], mx[o*2+1]);
    }
    void update(int o, int l, int r, int pos, int val) {
        if (l == r) { mx[o] = val; return; }
        int mid = (l+r)/2;
        if (pos <= mid) update(o*2, l, mid, pos, val);
        else update(o*2+1, mid+1, r, pos, val);
        mx[o] = max(mx[o*2], mx[o*2+1]);
    }
    int query(int o, int l, int r, int L, int R) {
        if (L <= l && r <= R) return mx[o];
        int mid = (l+r)/2, res = INT_MIN;
        if (L <= mid) res = max(res, query(o*2, l, mid, L, R));
        if (R > mid) res = max(res, query(o*2+1, mid+1, r, L, R));
        return res;
    }
};

輸入處理注意

• 多組測試，while (cin >> N >> M) 讀到 EOF
• 操作字符 Q/U 可能前有換行，用 cin >> op 自動跳過空白
• 學生編號從 1 開始，線段樹區間對應 [1,N]

複雜度

• 構建：O(N)
• 單次查詢/更新：O(log N)
• 總計：O((N+M) log N)，完全滿足限制

本題是線段樹「區間最值 + 單點更新」的標準模板題，代碼結構清晰，是後續變種題（區間加法、區間賦值等）的基礎。