记录编号	617735	评测结果	AAAAAAAAAA
题目名称	2961.[SYOI 2018] 简单的线段树	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	3.794 s
提交时间	2026-07-25 17:26:36	内存使用	5.79 MiB

#include <iostream>
using namespace std;
const int N = 1e5 + 5, tN = 4 * N;
int tr[tN], lz1[tN], lz2[tN];
#define mid ((l + r) / 2)
#define lc (u * 2)
#define rc (u * 2 + 1)
int n, m, p;
void lazy1(int u, int l, int r, int v) {
    lz1[u] = (1ll * lz1[u] + v) % p;
    tr[u] = (tr[u] + 1ll * (r - l + 1) * v % p) % p;
}
void lazy2(int u, int l, int r, int v) {
    lz2[u] = 1ll * lz2[u] * v % p;
    lz1[u] = 1ll * lz1[u] * v % p;
    tr[u] = 1ll * tr[u] * v % p;
}
void pd(int u, int l, int r) {
    if (lz2[u] != 1) {
        lazy2(lc, l, mid, lz2[u]);
        lazy2(rc, mid + 1, r, lz2[u]);
    }
    if (lz1[u]) {
        lazy1(lc, l, mid, lz1[u]);
        lazy1(rc, mid + 1, r, lz1[u]);
    }
    lz1[u] = 0;
    lz2[u] = 1;
}
void build(int u, int l, int r) {
    lz2[u] = 1;
    if (l == r) {
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
}
void upd1(int u, int l, int r, int xl, int xr, int v) {
    if (xl <= l && r <= xr) {
        lazy1(u, l, r, v);
        return;
    }
    pd(u, l, r);
    if (xl <= mid) upd1(lc, l, mid, xl, xr, v);
    if (mid + 1 <= xr) upd1(rc, mid + 1, r, xl, xr, v);
    tr[u] = (1ll * tr[lc] + tr[rc]) % p;
}
void upd2(int u, int l, int r, int xl, int xr, int v) {
    if (xl <= l && r <= xr) {
        lazy2(u, l, r, v);
        return;
    }
    pd(u, l, r);
    if (xl <= mid) upd2(lc, l, mid, xl, xr, v);
    if (mid + 1 <= xr) upd2(rc, mid + 1, r, xl, xr, v);
    tr[u] = (1ll * tr[lc] + tr[rc]) % p;
}
int query(int u, int l, int r, int xl, int xr) {
    if (r < xl || xr < l) return 0;
    if (xl <= l && r <= xr) {
        return tr[u];
    }
    pd(u, l, r);
    return (1ll * query(lc, l, mid, xl, xr) + query(rc, mid + 1, r, xl, xr)) % p;
}
int main() {
    cin >> n >> m >> p;
    build(1, 1, n);
    while (m--) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            upd1(1, 1, n, l, r, x);
        }
        if (op == 2) {
            cin >> x;
            upd2(1, 1, n, l, r, x);
        }
        if (op == 3) {
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}