HDU 4107 線段樹區間加法：維護最大/最小值與懶標記

HDU 4107 線段樹「水題」實戰

維護一個長度 n 的陣列，支援區間加值操作，查詢最終每個位置的值。節點存儲區間最大值 large、最小值 few、懶標記 add。關鍵優化：若區間 few >= k 整段加 2x；若 large < k 整段加 x；否則下推懶標記遞歸更新。

節點結構與操作

struct Node { int large, few, add; } seg[4*MAXN];

void push_down(int rt) {
    if (seg[rt].add) {
        seg[rt<<1].few   += seg[rt].add;
        seg[rt<<1].large += seg[rt].add;
        seg[rt<<1].add   += seg[rt].add;
        seg[rt<<1|1].few   += seg[rt].add;
        seg[rt<<1|1].large += seg[rt].add;
        seg[rt<<1|1].add   += seg[rt].add;
        seg[rt].add = 0;
    }
}

void update(int L, int R, int l, int r, int rt, int x) {
    if (L==l && R==r) {
        if (seg[rt].few >= k) { seg[rt].few += 2*x; seg[rt].large += 2*x; seg[rt].add += 2*x; return; }
        if (seg[rt].large < k) { seg[rt].few += x; seg[rt].large += x; seg[rt].add += x; return; }
    }
    push_down(rt);
    int mid = (L+R)>>1;
    if (r <= mid) update(L, mid, l, r, rt<<1, x);
    else if (l > mid) update(mid+1, R, l, r, rt<<1|1, x);
    else { update(L, mid, l, mid, rt<<1, x); update(mid+1, R, mid+1, r, rt<<1|1, x); }
    seg[rt].large = max(seg[rt<<1].large, seg[rt<<1|1].large);
    seg[rt].few   = min(seg[rt<<1].few,   seg[rt<<1|1].few);
}

輸出

中序遍歷輸出葉子節點 large 值。