HDU 4902 Nice Boat：線段樹區間更新維護區間最大最小值，支持賦值與 GCD 操作

HDU 4902 Nice Boat：線段樹區間更新維護最大最小值

題目大意

序列初始化後有 q 次操作：
1. 區間 [l,r] 賦值 x。
2. 區間 [l,r] 中 大於 x 的元素 與 x 取 gcd。
最終輸出整個序列。

線段樹設計

每節點存 Max, Min。
關鍵性質：若節點 Max == Min，說明該區間所有值相同，可直接打標記/操作，無需下推。
操作 1（賦值）：覆蓋區間 → 直接設 Max=Min=x，打標記。
操作 2（GCD）：若 Max < x → 直接返回；若 Max == Min > x → 整段取 gcd(Max,x)；否則下推繼續遞歸。
下推時機：當前節點值相同但操作區間僅覆蓋其一部分時，必須先將值下推給子節點。

核心代碼片段（C++）

struct Node { int Max, Min, l, r; } tr[4*MAXN];

void pushDown(int rt) {
    if (tr[rt].Max == tr[rt].Min) {
        tr[rt<<1].Max = tr[rt<<1].Min = tr[rt].Max;
        tr[rt<<1|1].Max = tr[rt<<1|1].Min = tr[rt].Max;
    }
}

void updateAssign(int rt, int L, int R, int x) {
    if (tr[rt].l == L && tr[rt].r == R) {
        tr[rt].Max = tr[rt].Min = x; return;
    }
    pushDown(rt);
    int mid = (tr[rt].l + tr[rt].r) >> 1;
    if (R <= mid) updateAssign(rt<<1, L, R, x);
    else if (L > mid) updateAssign(rt<<1|1, L, R, x);
    else { updateAssign(rt<<1, L, mid, x); updateAssign(rt<<1|1, mid+1, R, x); }
    tr[rt].Max = max(tr[rt<<1].Max, tr[rt<<1|1].Max);
    tr[rt].Min = min(tr[rt<<1].Min, tr[rt<<1|1].Min);
}

void updateGcd(int rt, int L, int R, int x) {
    if (tr[rt].l == L && tr[rt].r == R) {
        if (tr[rt].Max < x) return;
        if (tr[rt].Max == tr[rt].Min) {
            if (tr[rt].Max > x) tr[rt].Max = tr[rt].Min = gcd(tr[rt].Max, x);
            return;
        }
    }
    pushDown(rt);
    int mid = (tr[rt].l + tr[rt].r) >> 1;
    if (R <= mid) updateGcd(rt<<1, L, R, x);
    else if (L > mid) updateGcd(rt<<1|1, L, R, x);
    else { updateGcd(rt<<1, L, mid, x); updateGcd(rt<<1|1, mid+1, R, x); }
    tr[rt].Max = max(tr[rt<<1].Max, tr[rt<<1|1].Max);
    tr[rt].Min = min(tr[rt<<1].Min, tr[rt<<1|1].Min);
}

複雜度與技巧

• 區間賦值 + 區間條件 GCD，利用 Max==Min 剪枝，實際運行極快。
• 輸出時逐點查詢 O(n log n)，或中序遍歷收集 O(n)。
• 注意 pushDown 只在必要時調用，避免不必要的遞歸開銷。

本題展示了線段樹「維護區間極值 + 條件批量更新」的高級用法，是區間操作問題的優秀範例。