如题，已知一个数列 a，你需要进行下面三种操作：

将某区间每一个数乘上 x；
将某区间每一个数加上 x；
求出某区间每一个数的和。

输入格式

第一行包含三个整数 n,q,m，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值 ai​。

接下来 q 行每行包含若干个整数，表示一个操作，具体如下：

操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数乘上 k。

操作 2： 格式：2 x y k 含义：将区间 [x,y] 内每个数加上 k。

操作 3： 格式：3 x y 含义：输出区间 [x,y] 内每个数的和对 m 取模所得的结果。 【数据范围】

对于 30% 的数据：n≤8，q≤10。 对于 70% 的数据：n≤103，q≤104。 对于 100% 的数据：1≤n≤105，1≤q≤105,1≤ai​,k≤104。

// 维护序列
// P3373
#include <iostream>
#define lc u << 1
#define rc u << 1 | 1
#define LL long long

using namespace std;

const int N = 1e5 + 1023;
int n, q, m, w[N];

struct Tree {
    int l, r;
    LL sum;
    LL add, mul;
}tr[N << 2];

inline void pushup(int u) { tr[u].sum = (tr[lc].sum + tr[rc].sum) % q; }

inline void calc(Tree &t, LL m, LL a) {
    t.sum = (t.sum * m + t.add * (t.r - t.l + 1)) % q;
    t.mul = t.mul * m % q;
    t.add = (t.add * m + a) % q;
}

inline void pushdown(int u) {
    calc(tr[lc], tr[u].mul, tr[u].add);
    calc(tr[rc], tr[u].mul, tr[u].add);
    tr[u].add = 0;
    tr[u].mul = 1;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, 0, 1};
    if (l == r) {
        tr[u].sum = w[l] % q;
        return;
    }
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    pushup(u);
}

void change(int u, int l, int r, LL m, LL a) {
    //cout << tr[u].l << ' ' << tr[u].r << '\n' ;
    if (l <= tr[u].l && tr[u].r <= r) {
        calc(tr[u], m, a);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) change(lc, l, r, m, a);
    if (r > mid) change(rc, l, r, m, a);
    pushup(u);
}

LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    LL ans = 0, mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) (ans += query(lc, l, r)) %= q;
    if (r > mid) (ans += query(rc, l, r)) %= q;
    return ans;
}

int main()
{
    cin >> n >> m;
    cin >> q;
    for (int i = 1; i <= n; i++) cin >> w[i];
    build(1, 1, n);
    //cin >> m;

    for (int k, l, r; m--;) {
        LL v;
        cin >> k >> l >> r;
        if (k < 3) {
            cin >> v;
            change(1, l, r, k == 1 ? v : 1, k == 2 ? v : 0);
        } else {
            cout << query(1, l, r) << '\n';
        }
    }

    return 0;
}

修改