DDOSvoid's Blog

Luogu P3373 【模板】线段树 2

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟
区间乘，区间加，区间求和

题目描述

https://www.luogu.com.cn/problem/P3373

区间乘，区间加，区间求和

Solution

首先我们肯定要维护两个标记，add和mul

然后我们考虑标记优先级

注意到标记优先级的本质在于标记下方时对子节点区间和的影响

乘法优先，v = v * mul + add * len

加法优先，v = (v + add * len) * mul

由于加法优先造成精度损失，下面不做考虑

注意到我们只需要考虑pushdown操作，因为区间加和区间乘的修改与pushdown时对于子节点标记的修改的本质是一样的

在乘法优先的情况下（加下划线表示子节点的标记

_mul = _mul * mul

_add = _add * mul + add

最终代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <cstdio>
#define maxn 100010
#define ll long long
using namespace std;

int n, m, p, a[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct seg {
    int v, add, mul;
} T[maxn * 4];
inline void maintain(int i) { T[i].v = (T[lc].v + T[rc].v) % p; }

void build(int i, int l, int r) {
    T[i].add = 0; T[i].mul = 1;
    if (l == r) return (void) (T[i].v = a[l]);
    int m = l + r >> 1; 
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update_add(int i, int l, int r, ll v) {
    T[i].v = ((r - l + 1) * v + T[i].v) % p;
    T[i].add = (T[i].add + v) % p;
}

inline void Update_mul(int i, int l, int r, ll v) {
    T[i].v = T[i].v * v % p;
    T[i].mul = T[i].mul * v % p;
    T[i].add = T[i].add * v % p;
}

inline void pushdown(int i, int l, int r) {
    int &add = T[i].add, &mul = T[i].mul, m = l + r >> 1;

    Update_mul(lc, l, m, mul); Update_mul(rc, m + 1, r, mul);

    Update_add(lc, l, m, add); Update_add(rc, m + 1, r, add);

    mul = 1; add = 0;
}

void update_add(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update_add(i, l, r, v);
    int m = l + r >> 1; pushdown(i, l, r);
    update_add(lc, l, m, L, R, v); update_add(rc, m + 1, r, L, R, v);
    maintain(i);
}

void update_mul(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update_mul(i, l, r, v);
    int m = l + r >> 1; pushdown(i, l, r);
    update_mul(lc, l, m, L, R, v); update_mul(rc, m + 1, r, L, R, v);
    maintain(i);
}

int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1; pushdown(i, l, r);
    return (query(lc, l, m, L, R) + query(rc, m + 1, r, L, R)) % p;
}

inline void solve_1() {
    int l, r, v; scanf("%d%d%d", &l, &r, &v);
    update_mul(1, 1, n, l, r, v);
}

inline void solve_2() {
    int l, r, v; scanf("%d%d%d", &l, &r, &v);
    update_add(1, 1, n, l, r, v);
}

inline void solve_3() {
    int l, r; scanf("%d%d", &l, &r);
    printf("%lld\n", query(1, 1, n, l, r));
}

int main() {
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int opt; scanf("%d", &opt);
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        }
    }
    return 0;
}