Codeforces 85D Sum of Medians：線段樹維護模 5 余數和 (右移標記 + 單點更新)

問題

動態集合支持：
add x、del x、sum (輸出排序後下標 ≡ 3 (mod 5) 的元素和)。n ≤ 1e5。

核心思想：線段樹節點存 5 個和 + 移位標記

離散化所有出現的值。線段樹葉子對應一個離散值。內部節點維護 k[0..4]：該區間內元素排序後，下標 %5 == r 的和。
插入/刪除一個值時，該值右側所有元素下標 +1 → 余數循環右移 1 位。用 mov 標記懶惰傳播：pushup 時將左右子節點的 k 數組按 mov 旋轉合併。

節點結構與 Pushup

struct Node {
    int l, r, mov;
    long long k[5];
} t[4*N];

void pushup(int o) {
    if (t[o].l == t[o].r) { // 葉子：實際值在 k[mov%5]
        long long val=0;
        for (int i=0;i<5;i++) if (t[o].k[i]) val=t[o].k[i];
        if (!val) return;
        memset(t[o].k,0,sizeof t[o].k);
        t[o].k[t[o].mov%5] = val;
        return;
    }
    for (int i=0;i<5;i++)
        t[o].k[(i+t[o].mov)%5] = t[lson].k[i] + t[rson].k[i];
}

操作實現

區間右移 (插入/刪除觸發)

void setVal(int pos, long long val, int o=0) {
    if (t[o].l==t[o].r) {
        memset(t[o].k,0,sizeof t[o].k);
        if (val) t[o].k[t[o].mov%5] = val;
        return;
    }
    int mid=(t[o].l+t[o].r)>>1;
    if (pos<=mid) setVal(pos,val,lson);
    else setVal(pos,val,rson);
    pushup(o);
}

主流程

1. 讀入所有操作，離散化值 → rank。
2. 建樹 (區間 [0, maxRank])。
3. 處理操作：
   add x → addMov(rank, maxRank, +1); setVal(rank, x)
del x → addMov(rank, maxRank, -1); setVal(rank, 0)
sum → 輸出 t[0].k[3] (根節點模 5 為 3 的和)。

複雜度

O((n+q) log n)，每次操作 2 次線段樹走訪，極快。