线段树2 P3373。

样例错误。

#include <iostream>

using namespace std;

const int kMaxN = 1e5 + 7, kMaxM = (kMaxN * 4) + 7;

typedef long long ll;

int n, m, mod;
ll a[kMaxN], seg[kMaxM], lazy[kMaxM], lazy2[kMaxM];

int M(int l, int r) { return l + r >> 1; }
int L(int p) { return p << 1; }
int R(int p) { return p << 1 | 1; }

void B(int l, int r, int p) {
    lazy2[p] = 1;
    if (l == r) {
        seg[p] = a[l]; 
    } else { 
        int m = M(l, r);
        B(l, m, L(p)), B(m + 1, r, R(p));
        seg[p] = seg[L(p)] + seg[R(p)];
    }
    seg[p] %= mod;
}

void P(int p, int l, int r) {
    int m = M(l, r);
    seg[L(p)] = (seg[L(p)] * lazy2[p] + lazy[p] * (m - l + 1)) % mod;
    seg[R(p)] = (seg[R(p)] * lazy2[p] + lazy[p] * (r - m)) % mod;
    lazy2[L(p)] = lazy2[L(p)] * lazy2[p], lazy2[R(p)] = lazy2[R(p)] * lazy2[p] % mod;
    lazy[L(p)] = (lazy[L(p)] * lazy2[p] + lazy[p]) % mod, lazy[R(p)] = (lazy[R(p)] * lazy2[p] + lazy[p]) % mod;
    lazy2[p] = 1, lazy[p] = 0;
}

void U(int l, int r, ll d, int p, int s, int t) {
    if (s > r || l > t) { 
        return;
    } else if (l <= s && t <= r) { 
        seg[p] = (seg[p] + (t - s + 1) * d) % mod;
        lazy[p] = (lazy[d] + d) % mod;
    } else { 
        int m = M(s, t);
        P(p, s, t);
        U(l, r, d, L(p), s, m), U(l, r, d, R(p), m + 1, t);
        seg[p] = (seg[L(p)] % mod + seg[R(p)] % mod) % mod;
    }
}

void U2(int l, int r, ll d, int p, int s, int t) {
    if (s > r || l > t) { 
        return;
    } else if (l <= s && t <= r) { 
        seg[p] = seg[p] * d % mod;
        lazy2[p] = lazy2[p] * d % mod;
        lazy[p] = lazy[p] * d % mod;
    } else { 
        int m = M(s, t);
        P(p, s, t);
        U2(l, r, d, L(p), s, m), U2(l, r, d, R(p), m + 1, t);
        seg[p] = (seg[L(p)] % mod + seg[R(p)] % mod) % mod;
    }
}

ll Q(int l, int r, int p, int s, int t) {
    if (s > r || l > t) { 
        return 0;
    } else if (l <= s && t <= r) {
        return seg[p] % mod;
    } else {
        int m = M(s, t);
        P(p, s, t);
        return (Q(l, r, L(p), s, m) % mod + Q(l, r, R(p), m + 1, t) % mod) % mod;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> mod;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    B(1, n, 1);
    for (ll i = 1, op, x, y, k; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1) {
            cin >> k;
            U2(x, y, k, 1, 1, n);
        } else if (op == 2) {
            cin >> k;
            U(x, y, k, 1, 1, n);
        } else {
            cout << Q(x, y, 1, 1, n) << '\n';
        }
    }

    return 0;
}