【线段树入门】P3373 线段树 2(区间乘加)

//笔记-自用
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#define _CRT_SECURE_NO_WARNINGS
#define All(a) a.begin(),a.end()
#define INF 2147483647
#include<bits/stdc++.h>
#include<numeric>
using namespace std;
typedef unsigned long long ull;
#define int long long//再也不用担心开longlong了><
typedef pair<int, int>PII;

int mod;
#define lc p<<1
#define rc p<<1|1
const int N = 1e5 + 5;
struct node {
    int l, r, val, mul, add;
}tr[N*4];
int w[N];

void pushup(int p) {//不变
    tr[p].val = tr[lc].val + tr[rc].val;
    tr[p].val %= mod;
}

void pushdown(int p) {//先乘后加 mul懒标记重置为1 区间修改：区间值*mul+区间长*add  mul懒标记：乘上mul  add懒标记：乘上mul并且加上add
    tr[lc].val = tr[p].mul * tr[lc].val + tr[p].add * (tr[lc].r - tr[lc].l + 1);
    tr[rc].val = tr[p].mul * tr[rc].val + tr[p].add * (tr[rc].r - tr[rc].l + 1);
    tr[lc].mul *= tr[p].mul;
    tr[rc].mul *= tr[p].mul;
    tr[lc].add = (tr[lc].add * tr[p].mul) + tr[p].add;
    tr[rc].add = (tr[rc].add * tr[p].mul) + tr[p].add;
    tr[lc].val %= mod; tr[rc].val %= mod;
    tr[lc].mul %= mod; tr[rc].mul %= mod;
    tr[lc].add %= mod; tr[rc].add %= mod;
    tr[p].mul = 1;
    tr[p].add = 0;
}

void build(int p, int l, int r) {//不变 mul初始值为1
    tr[p] = { l,r,w[l],1,0 };
    if (l == r)return;
    int mid = tr[p].l + tr[p].r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(p);
}

void update(int p, int x, int y, int mul, int add) {//类似
    if (x <= tr[p].l && tr[p].r <= y) {
        tr[p].val = mul * tr[p].val + add*(tr[p].r-tr[p].l+1);
        tr[p].mul *= mul;
        tr[p].add = tr[p].add * mul + add;
        tr[p].val %= mod; tr[p].mul %= mod; tr[p].add %= mod;
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    pushdown(p);
    if (x <= mid)update(lc, x, y, mul, add);
    if (y > mid)update(rc, x, y, mul, add);
    pushup(p);
}


int query(int p, int x, int y) {//类似
    if (x <= tr[p].l && tr[p].r <= y) {        
        return tr[p].val;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    pushdown(p);
    int res = 0;
    if (x <= mid)res += query(lc, x, y);
    if (y > mid)res += query(rc, x, y);
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q;
    cin >> n >> q >> mod;
    for (int i = 1; i <= n; i++)cin >> w[i];
    build(1, 1, n);
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            int k;
            cin >> k;
            update(1, x, y, k, 0);
        }
        else if (op == 2) {
            int k;
            cin >> k;
            update(1, x, y, 1, k);
        }
        else {
            cout << query(1, x, y)%mod << "\n";
        }
    }

}