加法乘法线段树模板

P2023 [AHOI2009]维护序列

指定一个区间 加上或者乘以 V,

查询一个区间所有元素和%P

与纯加法线段树不同的是,lazy_tag 的传递

(x + y) * v = xv + yv。

所以每次乘法,都要把加法的lazy_tag * v
而加法与加法线段树的操作一样

#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;
const int MAXN = 100005 + 5;
LL N,P,M;
LL A[MAXN];
struct seg { LL l,r,v,lz,mz; } t[MAXN << 2];
LL lch(LL k) { return k << 1; };
LL rch(LL k) { return k << 1 | 1; };
inline void add(LL& a,LL b) { a = (a + b) % P; };
inline void mul(LL& a,LL b) { a = (a * b) % P; };
void push_up(LL k) { t[k].v = (t[lch(k)].v + t[rch(k)].v) % P; };
void push_down(LL k) {
    if (t[k].mz == 1 && !t[k].lz) return;
    LL mid = (t[k].r + t[k].l) >> 1,lz = t[k].lz,mz = t[k].mz;
    t[lch(k)].v = (t[lch(k)].v * mz + lz * (mid - t[k].l + 1))%P;
    t[rch(k)].v = (t[rch(k)].v * mz + lz * (t[k].r - mid))%P;
    mul(t[lch(k)].mz,mz);
    mul(t[rch(k)].mz,mz);
    t[lch(k)].lz = (t[lch(k)].lz * mz + lz) % P;
    t[rch(k)].lz = (t[rch(k)].lz * mz + lz) % P;
    t[k].lz = 0; t[k].mz = 1;
}
void build(LL k,LL l,LL r) {
    t[k].l = l,t[k].r = r,t[k].lz = 0,t[k].mz = 1;
    if (l == r) {
        t[k].v = A[l];
        return;
    }
    LL mid = (r + l) >> 1;
    build(lch(k),l,mid);
    build(rch(k),mid + 1,r);
    push_up(k);
}
void update(LL k,LL r,LL v,LL f) {
    if (t[k].l >= l && t[k].r <= r) {
        if (f == 1) {
            mul(t[k].v,v);
            mul(t[k].mz,v);
            mul(t[k].lz,v);
        }
        else {
            add(t[k].v,v * (t[k].r - t[k].l + 1));
            add(t[k].lz,v);
        }
        return;
    }
    push_down(k);
    if (t[lch(k)].r >= l) update(lch(k),f);
    if (t[rch(k)].l <= r) update(rch(k),f);
    push_up(k);
}
LL query(LL k,LL r) {
    LL ans = 0;
    if (t[k].l >= l && t[k].r <= r) return t[k].v;
    push_down(k);
    if (t[lch(k)].r >= l) add(ans,query(lch(k),r));
    if (t[rch(k)].l <= r) add(ans,query(rch(k),r));
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> P;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    build(1,1,N);
    LL a,b,c,d;
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> a;
        if (a == 1) {
            cin >> b >> c >> d;
            update(1,d,1);
        }
        else if (a == 2) {
            cin >> b >> c >> d;
            update(1,2);
        }
        else {
            cin >> b >> c;
            cout << query(1,c) << endl;
        }
    }
    return 0;
}