题目:P3373 【模板】线段树 2。

不知道为什么，样例也没过。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
typedef long long ll;
ll n, m, p, a[4 * MAXN], sum[4 * MAXN];
ll lazyp[4 * MAXN], lazym[4 * MAXN];
void pushup(ll id) {
    sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % p;
}
void pushdown(ll id, ll l, ll r){
    sum[id << 1] = (ll)(lazym[id] * sum[id << 1] + ((r - l + 1) * lazyp[id]) % p) % p;
    sum[id << 1 | 1] = (ll)(lazym[id] * sum[id << 1 | 1] + ((r - l + 1) * lazyp[id]) % p) % p;
    lazym[id << 1] = (ll)(lazym[id << 1] * lazym[id]) % p;
    lazym[id << 1 | 1] = (ll)(lazym[id << 1 | 1] * lazym[id]) % p;
    lazyp[id << 1] = (ll)(lazyp[id << 1] * lazym[id] + lazyp[id]) % p;
    lazyp[id << 1 | 1] = (ll)(lazyp[id << 1 | 1] * lazym[id] + lazyp[id]) % p;
    lazym[id] = 1, lazyp[id] = 0;
}
void build(int id, int l, int r) {
    if(l == r) {
        sum[id] = a[l] % p;
        return ;
    }
    ll mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(id);
}
void updatep(ll id, ll l, ll r, ll x, ll y, ll v) {
    if(x <= l && r <= y) {
        sum[id] = ((ll)(sum[id] + (r - l + 1) * v)) % p;
        lazyp[id] = (lazyp[id] + v) % p;
        return ; 
    }
    pushdown(id, l, r);
    ll mid = (l + r) >> 1;
    if(x <= mid) updatep(id << 1, l, mid, x, y, v);
    if(y > mid) updatep(id << 1 | 1, mid + 1, r, x, y, v);
    pushup(id);
}
void updatem(ll id, ll l, ll r, ll x, ll y, ll v) {
    if(x <= l && r <= y) {
        lazyp[id] = (lazyp[id] * v) % p;
        lazym[id] = (lazym[id] * v) % p;
        sum[id] = (sum[id] * v) % p;
        return ;
    }
    pushdown(id, l, r);
    ll mid = (l + r) >> 1;
    if(x <= mid) updatem(id << 1, l, mid, x, y, v);
    if(y > mid) updatem(id << 1 | 1, mid + 1, r, x, y, v);
    pushup(id);
}
ll query(ll id, ll l, ll r, ll x, ll y) {
    if(x <= l && r <= y) return sum[id];
    pushdown(id, l, r);
    ll ans = 0, mid = (l + r) >> 1;
    if(x <= mid) ans = (ans + query(id << 1, l, mid, x, y)) % p;
    if(y > mid) ans = (ans + query(id << 1 | 1, mid + 1, r, x, y)) % p;
    return ans;
}
int main() {
    cin >> n >> m >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for(int i = 1; i <= m; i++) {
        int c;
        cin >> c;
        if(c == 1) {
            ll x, y, v;
            scanf("%lld%lld%lld", &x, &y, &v);
            updatem(1, 1, n, x, y, v);
        }
        else if(c == 2) {
            ll x, y, v;
            scanf("%lld%lld%lld", &x, &y, &v);
            updatep(1, 1, n, x, y, v);
        } else {
            ll x, y;
            scanf("%lld%lld", &x, &y);
            cout << query(1, 1, n, x, y) << endl;
        }
    }
    return 0;
}