luogu P3373 【模板】线段树 2

结构体线段树原来正确率比用数组的高啊，原来用数组写的线段树写挂的结构体竟然过了，哇咔咔

以后就转坑结构体线段树了

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
const int maxm = 4e5 + 7;
int n, m, a[maxn];
ll mod;
struct node {
    int l, r, size;
    ll sum, lazy_add, lazy_mul;
} e[maxm];

int read() {
    int x = 0, f = 1; char s = getchar();
    for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}

void pushup(int rt) {
    e[rt].sum = (e[rt << 1].sum + e[rt << 1 | 1].sum) % mod;
}

void pushdown(int rt) {
    if (e[rt].lazy_add || e[rt].lazy_mul != 1) {
        /*
            mul1(x*mul2+add2)+add1
            mul1*mul2*x+mul1*add2+add1
        */
        e[rt << 1].sum     = ((e[rt << 1].sum     * e[rt].lazy_mul) % mod + (e[rt << 1].size  * e[rt].lazy_add) % mod) % mod;
        e[rt << 1 | 1].sum = ((e[rt << 1 | 1].sum * e[rt].lazy_mul) % mod + (e[rt << 1 | 1].size  * e[rt].lazy_add) % mod) % mod;

        e[rt << 1].lazy_add     = ((e[rt].lazy_mul * e[rt << 1].lazy_add) % mod     + e[rt].lazy_add) % mod;
        e[rt << 1 | 1].lazy_add = ((e[rt].lazy_mul * e[rt << 1 | 1].lazy_add) % mod + e[rt].lazy_add) % mod;

        e[rt << 1].lazy_mul     = e[rt].lazy_mul * e[rt << 1].lazy_mul % mod;
        e[rt << 1 | 1].lazy_mul = e[rt].lazy_mul * e[rt << 1 | 1].lazy_mul % mod;

        e[rt].lazy_add = 0;
        e[rt].lazy_mul = 1;
    }
}

void build(int l, int r, int rt) {
    e[rt].l = l, e[rt].r = r, e[rt].size = r - l + 1,e[rt].lazy_mul=1;
    if (l == r) {
        e[rt].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}

void update_add(int L, int R, int k, int rt) {
    if (L <= e[rt].l && e[rt].r <= R) {
        /*
            x*a+b+c
            x*a+b+c
        */
        e[rt].sum = (e[rt].sum + (e[rt].size * k) % mod ) % mod;
        e[rt].lazy_add = (e[rt].lazy_add + k) % mod;
        return;
    }
    pushdown(rt);
    int mid = (e[rt].l + e[rt].r) >> 1;
    if (L <= mid) update_add(L, R, k, rt << 1);
    if (R > mid) update_add(L, R, k, rt << 1 | 1);
    pushup(rt);
}

void update_mul(int L, int R, int k, int rt) {
    if (L <= e[rt].l && e[rt].r <= R) {
        /*
            c*(a*x+b)
            c*a*x+c*b
        */
        e[rt].sum = e[rt].sum * k % mod;
        e[rt].lazy_mul = e[rt].lazy_mul * k % mod;
        e[rt].lazy_add = e[rt].lazy_add * k % mod;
        return;
    }
    pushdown(rt);
    int mid = (e[rt].l + e[rt].r) >> 1;
    if (L <= mid) update_mul(L, R, k, rt << 1);
    if (R > mid) update_mul(L, R, k, rt << 1 | 1);
    pushup(rt);
}

ll query(int L, int R, int rt) {
    if (L <= e[rt].l && e[rt].r <= R) {
        return e[rt].sum;
    }
    pushdown(rt);
    int mid = (e[rt].l + e[rt].r) >> 1;
    ll ans = 0;
    if (L <= mid) ans = query(L, R, rt << 1);
    if (R > mid) ans = (ans + query(L, R, rt << 1 | 1)) % mod;
    pushup(rt);
    return ans;
}

int main() {
    //freopen("a.in","r",stdin);
    n = read(), m = read(), mod = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    build(1, n, 1);
    for (int i = 1; i <= m ; ++ i) {
        int tmp = read();
        int a,b,c;
        if (tmp == 1) {
            a=read(),b=read(),c=read();
            update_mul(a, b, c, 1);
        } else if (tmp == 2) {
            a=read(),b=read(),c=read();
            update_add(a, b, c, 1);
        } else if (tmp == 3) {
            int a=read(),b=read();
            printf("%lld\n", query(a, b, 1));
        }
    }
    return 0;
}