线段树

重点

1. 两种操作合并成一种
2. 合并后的操作需要注意蓝标记向下传递的时候，的更新的情况

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
typedef long long ll;
int n, m, p;
int a[N];
struct node {
    int l, r;
    ll sum, mul, add;
} tr[N * 4];

void eval(node &root, int mul, int add) {
    root.sum = (root.sum * mul % p + (ll)(root.r - root.l + 1) * add) % p;
    root.mul = root.mul * mul % p;
    root.add = (root.add * mul % p + add) % p;
}

void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown(int u) {
    eval(tr[u << 1], tr[u].mul, tr[u].add);
    eval(tr[u << 1 | 1], tr[u].mul, tr[u].add);
    tr[u].add = 0;
    tr[u].mul = 1;
}

void build (int u, int l, int r) {
    if (l == r) tr[u] = {l, r, a[l] % p, 1, 0};
    else {
        tr[u] = {l, r, 0, 1, 0};  // 初始化，太坑了
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int mul, int add) {
    if (tr[u].l >= l && tr[u].r <= r) {
        eval(tr[u], mul, add);
    } else {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (l <= mid) modify(u << 1, l, r, mul, add);
        if (r > mid) modify(u << 1 | 1, l, r, mul, add);
        pushup(u);
    }
}

ll query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll res = 0;
    if (l <= mid) res += query(u << 1, l, r) % p;
    if (r > mid) res = (res + query(u << 1 | 1, l, r)) % p;
    return res;
}

int main() {
    cin >> n >> p;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    int k, t, g, c;
    cin >> m;
    while (m--) {
        scanf("%d%d%d", &k, &t, &g);
        if (k == 1 || k == 2) {
            scanf("%d", &c);
            if (k == 1) modify(1, t, g, c, 0);
            else modify(1, t, g, 1, c);
        } else if (k == 3) {
            printf("%lld\n", query(1, t, g));
        }
    }
    return 0;
}