BZOJ 1798: [Ahoi2009]Seq 維護序列seq （線段樹乘法加法的混合操作）

BZOJ 1798: [Ahoi2009]Seq 維護序列seq （線段樹乘法加法的混合操作）

題目：點擊打開鏈接

大意：一個數組，三個操作，第一種是區間[a,b]每個數乘乘，第二種是區間[a,b]每個數加c，第三種是查詢[a,b]區間的和並對p取摸。

兩種操作就不能簡單的只往下傳標記。每次傳乘法標記時，要把加法標記同時乘上乘法標記，例如某個區間先進來一個加法標記add，之後又進來一個乘法標記mul。

那麼結果為(x + add) * mul = x * mul + add * mul。這樣向下傳標記的時候就相對獨立。遞歸邊界更新加法標記之前先乘上該節點的mul，左右兒子down的時候先將兒子的add乘上本節點的mul。

最後說一下sum，比如本節點的存在加法標記x和乘法標記y，並且是先加上x，再乘上y，則左兒子的sum要更新為(sum+x)*y。由於乘法標記傳到本節點的時候更新了加法標記，x = x*y，所以sum[o<<1] = (左區間的長度*x) + sum[o<<1]*y。

/**************************************************************
    Problem: 1798
    User: __ElemenT
    Language: C++
    Result: Accepted
    Time:4676 ms
    Memory:10184 kb
****************************************************************/
 
#include 
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
typedef long long LL;
const int maxn = 100005;
 
int n, a, b, c, k, q;
LL sum[maxn<<2], add[maxn<<2], mul[maxn<<2], p;
 
void up(int o) {
    sum[o] = (sum[o<<1]+sum[o<<1|1]) %p;
}
 
void build(int o, int l, int r) {
    add[o] = 0, mul[o] = 1;
    if(l == r) {
        scanf("%lld", &sum[o]);
        return;
    }
    int m = (l+r) >> 1;
    build(lson);
    build(rson);
    up(o);
}
 
void down(int o, int len) {
   // if(add[o] != 0 && mul[o] != 1) {
        add[o<<1] = (add[o<<1] * mul[o] + add[o]) %p;
        add[o<<1|1] = (add[o<<1|1] * mul[o] + add[o]) %p;
        mul[o<<1] = mul[o<<1] * mul[o] %p;
        mul[o<<1|1] = mul[o<<1|1] * mul[o] %p;
        sum[o<<1] = (sum[o<<1] * mul[o] + add[o] * (len-(len>>1))) %p;
        sum[o<<1|1] = (sum[o<<1|1] * mul[o] + add[o] * (len>>1)) %p;
        add[o] = 0, mul[o] = 1;
   // }
}
 
void update(int o, int l, int r, int op) {
    if(a <= l && r <= b) {
        if(op == 1) {
            add[o] = add[o]*c %p;
            mul[o] = mul[o]*c %p;
            sum[o] = sum[o]*c %p;
        } else {
            add[o] = (add[o] + c) %p;
            sum[o] = (sum[o] + (LL)c*(r-l+1)) %p;
        }
        return;
    }
    down(o, r-l+1);
    int m = (l+r) >> 1;
    if(a <= m) update(lson, op);
    if(m < b ) update(rson, op);
    up(o);
}
 
LL query(int o, int l, int r) {
    if(a <= l && r <= b) return sum[o] %p;
    down(o, r-l+1);
    int m = (l+r) >> 1;
    LL ans = 0;
    if(a <= m) ans = query(lson);
    if(m < b ) ans += query(rson);
    return ans %p;
}
 
int main()
{
    scanf("%d%lld", &n, &p);
    build(1, 1, n);
    scanf("%d", &q);
    while(q--) {
        scanf("%d%d%d", &k, &a, &b);
        if(k != 3) {
            scanf("%d", &c);
            update(1, 1, n, k);
        } else printf("%lld\n", query(1, 1, n));
    }
    return 0;
}