m+7炒鸡吴迪题解

#include <bits/stdc++.h>

#define MAXN 500005
#define ll long long

using namespace std;

int n, m, mod;
int a[MAXN];

struct tree {
    ll sum, add, mul;
    int l, r;
} s[MAXN * 4];

void update(int pos) {
    s[pos].sum = (s[pos << 1].sum + s[pos << 1 | 1].sum) % mod;
    return;
}

void pushdown(int pos) {
    s[pos << 1].sum = (s[pos << 1].sum * s[pos].mul + s[pos].add * (s[pos << 1].r - s[pos << 1].l + 1)) % mod;
    s[pos << 1 | 1].sum = (s[pos << 1 | 1].sum * s[pos].mul + s[pos].add * (s[pos << 1 | 1].r - s[pos << 1 | 1].l + 1)) % mod;
    
    s[pos << 1].mul = (s[pos << 1].mul * s[pos].mul) % mod;
    s[pos << 1 | 1].mul = (s[pos << 1 | 1].mul * s[pos].mul) % mod;
    
    s[pos << 1].add = (s[pos << 1].add * s[pos].mul + s[pos].add) % mod;
    s[pos << 1 | 1].add = (s[pos << 1 | 1].add * s[pos].mul + s[pos].add) % mod;
    
    s[pos].add = 0;
    s[pos].mul = 1;
    return; 
}

void build(int pos, int l, int r) {
    s[pos].l = l;
    s[pos].r = r;
    s[pos].mul = 1;
    
    if (l == r) {
        s[pos].sum = a[l] % mod;
        return;
    }
    
    int mid = (l + r) >> 1;
    build(pos << 1, l, mid);
    build(pos << 1 | 1, mid + 1, r);
    update(pos);
    return;
}

void CM(int pos, int x, int y, int k) { // 区间乘法
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add * k) % mod;
        s[pos].mul = (s[pos].mul * k) % mod;
        s[pos].sum = (s[pos].sum * k) % mod;
        return;
    }
    
    pushdown(pos);
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) CM(pos<< 1, x, y, k);
    if (y > mid) CM(pos<< 1 | 1, x, y, k);
    update(pos);
    return;
}

void CA(int pos, int x, int y, int k) {
    if (x <= s[pos].l && s[pos].r <= y) {
        s[pos].add = (s[pos].add + k) % mod;
        s[pos].sum = (s[pos].sum + k * (s[pos].r - s[pos].l + 1)) % mod;
        return;
    }
    
    pushdown(pos);
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) CA(pos << 1, x, y, k);
    if (y > mid) CA(pos << 1 | 1, x, y, k);
    update(pos);
    return;
}

ll Ask(int pos, int x, int y) {
    if (x <= s[pos].l && s[pos].r <= y) {
        return s[pos].sum;
    }
    
    pushdown(pos);
    ll val = 0;
    int mid = (s[pos].l + s[pos].r) >> 1;
    if (x <= mid) val = (val + Ask(pos << 1, x, y)) % mod;
    if (y > mid) val = (val + Ask(pos << 1 | 1, x, y)) % mod;
    return val;
}

int main() {
    scanf("%d%d%d", &n, &m, &mod);
    
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; i++){
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) {
            int k;
            scanf("%d", &k);
            CM(1, x, y, k);
        }
        if (opt == 2) {
            int k;
            scanf("%d", &k);
            CA(1, x, y, k);
        }
        if (opt == 3) {
            printf("%lld\n", (Ask(1, x, y) % mod + mod) % mod);
        }
    }
    
    return 0;
}