BZOJ 1798 [Ahoi2009] Seq 維護序列：線段樹雙標記 (乘法+加法) 延遲傳播詳解

問題描述

序列初始長度 n ≤ 10^5，支持三種操作：
1) 區間 [a,b] 每個數乘以 c
2) 區間 [a,b] 每個數加 c
3) 查詢區間 [a,b] 和對 p 取模
操作數 q ≤ 10^5，p 為模數 (非必質數)。

關鍵難點：兩種標記的相互影響

若節點已有加法標記 add，再乘以 mul，實際效果為 (x + add) * mul = x*mul + add*mul。因此 下推乘法標記時，必須同步更新加法標記：child.add = child.add * mul + add，child.mul = child.mul * mul。

線段樹節點結構

struct Node {
    long long sum; // 區間和
    long long add; // 待加標記，初始 0
    long long mul; // 待乘標記，初始 1
};

核心操作實現

下推

void pushdown(int o, int len) {
    if (tree[o].mul != 1 || tree[o].add != 0) {
        // 左子節點
        apply(o<<1, tree[o].mul, tree[o].add, len - (len>>1));
        // 右子節點
        apply(o<<1|1, tree[o].mul, tree[o].add, len>>1);
        tree[o].mul = 1;
        tree[o].add = 0;
    }
}
void apply(int o, long long mul, long long add, int childLen) {
    tree[o].sum = (tree[o].sum * mul + add * childLen) % MOD;
    tree[o].add = (tree[o].add * mul + add) % MOD;
    tree[o].mul = (tree[o].mul * mul) % MOD;
}

區間更新

void update(int o, int l, int r, int ql, int qr, int op, long long val) {
    if (ql <= l && r <= qr) {
        if (op == 1) apply(o, val, 0, r-l+1); // 乘法
        else apply(o, 1, val, r-l+1);         // 加法
        return;
    }
    pushdown(o, r-l+1);
    int mid = (l+r)>>1;
    if (ql <= mid) update(o<<1, l, mid, ql, qr, op, val);
    if (qr > mid) update(o<<1|1, mid+1, r, ql, qr, op, val);
    tree[o].sum = (tree[o<<1].sum + tree[o<<1|1].sum) % MOD;
}

區間查詢

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[o].sum;
    pushdown(o, r-l+1);
    int mid = (l+r)>>1;
    long long res = 0;
    if (ql <= mid) res = (res + query(o<<1, l, mid, ql, qr)) % MOD;
    if (qr > mid) res = (res + query(o<<1|1, mid+1, r, ql, qr)) % MOD;
    return res;
}

複雜度與注意點

• 時間 O((n+q) log n)，空間 O(n)。
• 所有中間結果須 % MOD，防止溢出 (用 long long)。
• 建樹時 mul=1, add=0；葉子節點 sum 直接讀入。
• 測試數據可能含多組，需循環讀至 EOF。