传送门：P3373 【模板】线段树 2

更佳的阅读体验：洛谷 P3373 题解

请注意，为了更好理解本篇题解，你需要通过P3372 【模板】线段树 1。

简要题意：给定长度为 $n$ 的序列 $a$，你需要进行 $q$ 次操作，包括区间乘、区间加、区间求和。

算法介绍

看到区间操作，第一反应应该想到使用线段树了。可是本题相比线段树 1 多了一个区间乘的操作，我们需要考虑如何处理区间乘操作。

为了保证复杂度正确，我们还是需要使用懒标记（lazy tag），但此时发现单独一个维护区间加操作的懒标记 $add$ 似乎无法满足需求，于是想到：再加一个懒标记 $mul$，用于维护区间乘操作。

那么此时问题又来了，我们应该如何完成 pushdown 操作呢？

显然，考虑到乘法和加法的优先级问题，我们不能再像只有区间加的时候一样直接乘上去。

由此我们想到，在计算区间和的时候，先乘再加，即先将原有的区间和乘上 $mul$，再加上 $add$。下方懒标记的过程也同理，确保遵循“先乘再加”的原则即可。

代码实现

为了提高代码的可读性，此处使用结构体封装线段树。

#include <iostream>
#define ls(p) t[p].lson
#define rs(p) t[p].rson
#define mid (l + r >> 1)
using namespace std;
using ll = long long;

const int N = 1e5 + 10;
int n, q, m, op, x, y;
ll k, a[N];
struct seg_tree {
    int rt[N << 1], tot;
    struct node {
        int lson, rson;
        ll sum, add, mul;
    } t[N << 1];

    void pushup(int p) {
        t[p].sum = (t[ls(p)].sum + t[rs(p)].sum) % m;
    }

    void build(int &p, int l, int r) {
        p = ++tot;
        t[p].mul = 1;
        if (l == r) return t[p].sum = a[l], void();
        build(ls(p), l, mid);
        build(rs(p), mid + 1, r);
        pushup(p);
    }

    void maketag(int p, int len, ll addx, ll mulx) {
        t[p].sum = (t[p].sum * mulx % m + addx * len % m) % m;
        t[p].add = (t[p].add * mulx % m + addx) % m;
        t[p].mul = t[p].mul * mulx % m;
    }

    void pushdown(int p, int l, int r) {
        maketag(ls(p), mid - l + 1, t[p].add, t[p].mul);
        maketag(rs(p), r - mid, t[p].add, t[p].mul);
        t[p].add = 0, t[p].mul = 1;
    }

    int query(int p, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (l >= L && r <= R) return t[p].sum;
        pushdown(p, l, r);
        return (query(ls(p), l, mid, L, R) + query(rs(p), mid + 1, r, L, R)) % m;
    }

    void update(int p, int l, int r, int L, int R, ll addx, ll mulx) {
        if (l > R || r < L) return;
        if (l >= L && r <= R) return maketag(p, r - l + 1, addx, mulx);
        pushdown(p, l, r);
        update(ls(p), l, mid, L, R, addx, mulx);
        update(rs(p), mid + 1, r, L, R, addx, mulx);
        pushup(p);
    }
} tree;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> q >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    tree.build(tree.rt[1], 1, n);
    while (q--) {
        cin >> op >> x >> y;
        if (op == 1) cin >> k, tree.update(tree.rt[1], 1, n, x, y, 0, k);
        else if (op == 2) cin >> k, tree.update(tree.rt[1], 1, n, x, y, k, 1);
        else cout << tree.query(tree.rt[1], 1, n, x, y) << '\n';
    } return 0;
}