思路与算法

用线段树维护区间和，并把懒标记统一写成仿射变换 x→mulx+add。区间乘c等价于(mul,add)=(c,0)，区间加c等价于(1,c)。把新变换应用到长度len的节点时，区间和变为 summul+add*len；同时把新变换复合到已有懒标记后面。所有运算对P取模。

正确性说明

若旧标记为x→xm+a，新操作为y→yu+v，复合后是x→x*(mu)+(au+v)。因此乘标记乘u，加标记也必须先乘u再加v。节点和按相同变换作用于区间内每个元素，得到sumu+lenv。下传这一正确的复合变换后，子节点和真实数组保持一致，递归区间查询便得到正确结果。

复杂度

建树 O(N)，每次更新或查询 O(log N)，总时间 O(N+M log N)，空间 O(N)。

易错点

先加后乘与先乘后加不同。乘0后旧信息被清除，但后续加法仍须保留。P=1时所有回答均为0。中间乘积使用long long，并及时取模，避免int溢出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Seg {
    int n;
    long long P;
    vector<long long> s, mul, add;
    Seg(int n, long long P) : n(n), P(P), s(4 * n), mul(4 * n, 1), add(4 * n) {
    }
    void apply(int u, int len, long long a, long long b) {
        s[u] = (s[u] * a + b * len) % P;
        mul[u] = mul[u] * a % P;
        add[u] = (add[u] * a + b) % P;
    }
    void build(int u, int l, int r, vector<long long> &a) {
        if (l == r) {
            s[u] = a[l] % P;
            return;
        }
        int mid = (l + r) / 2;
        build(u * 2, l, mid, a);
        build(u * 2 + 1, mid + 1, r, a);
        s[u] = (s[u * 2] + s[u * 2 + 1]) % P;
    }
    void push(int u, int l, int r) {
        if (l == r)
            return;
        int mid = (l + r) / 2;
        apply(u * 2, mid - l + 1, mul[u], add[u]);
        apply(u * 2 + 1, r - mid, mul[u], add[u]);
        mul[u] = 1;
        add[u] = 0;
    }
    void update(int u, int l, int r, int L, int R, long long a, long long b) {
        if (L <= l && r <= R) {
            apply(u, r - l + 1, a, b);
            return;
        }
        push(u, l, r);
        int mid = (l + r) / 2;
        if (L <= mid)
            update(u * 2, l, mid, L, R, a, b);
        if (R > mid)
            update(u * 2 + 1, mid + 1, r, L, R, a, b);
        s[u] = (s[u * 2] + s[u * 2 + 1]) % P;
    }
    long long query(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R)
            return s[u];
        push(u, l, r);
        int mid = (l + r) / 2;
        long long ans = 0;
        if (L <= mid)
            ans += query(u * 2, l, mid, L, R);
        if (R > mid)
            ans += query(u * 2 + 1, mid + 1, r, L, R);
        return ans % P;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long P;
    cin >> n >> P;
    vector<long long> a(n);
    for (auto &v : a)
        cin >> v;
    Seg t(n, P);
    t.build(1, 0, n - 1, a);
    int m;
    cin >> m;
    while (m--) {
        int op, l, r;
        long long c;
        cin >> op >> l >> r;
        --l;
        --r;
        if (op == 3)
            cout << t.query(1, 0, n - 1, l, r) << '\n';
        else {
            cin >> c;
            c %= P;
            t.update(1, 0, n - 1, l, r, op == 1 ? c : 1, op == 2 ? c : 0);
        }
    }
}