Luogu P3373: 线段树

题目

点我去找题目
大意就是有若干数组成的一个序列，有三种操作，一种是让一个区间内每个数字加上一个数；一种是让一个区间内每个数字都乘上一个数字；最后一种是查询。

思路

这其实是一道模版题，只不过相比最基础的线段树来说多了一种标记，那我们要解决的主要问题就是如何来维护这两种标记。
维护时的主要问题有以下两个：

1. 打标记的时候如何打
2. 标记下放的时候如何下放

矛盾的地方实际上就是，我在添加一种标记的时候，需不需要处理另一种标记；如果需要，该怎么处理才能使这棵树的正确性不变。
我们可以通过人为设定优先级的方式来解决：
对于一个节点k, f[k]代表区间和, madd[k]代表加法标记, mmul[k]代表乘法标记

1. 先考虑加法优先
   则对于节点k的子节点来说, 规定在更新子节点的时候，先处理父节点传下来的加法标记，再处理父节点传下来的乘法标记，即先加后乘。那么我们在给一个区间加上数字z的时候，由小学学过的四则运算的性质，我们可以得到madd[k] += z/mmul[k]。明显这样处理之后按照规定的优先级就可以正确更新子节点的值了。
2. 考虑乘法优先
   对于节点k的子节点来说, 规定在更新子节点的时候，先处理父节点传下来的乘法标记，再处理父节点传下来的加法标记，即先乘后加。那么我们在给一个区间乘上数字z的时候，按照乘法分配律可以得到madd[k] *= z。

对于上面的两种做法，第一种做法由于存在整数的除法，故可能存在精度的问题；第二种做法虽然可能造成溢出，但是题目里说明了答案需要取模，所以溢出的问题也解决了，那我们就选择第二种做法。

代码

#include <cstdio>

using namespace std;
#define lc k<<1
#define rc k<<1|1
typedef long long ll;

const int maxn = 1e5+5;
ll a[maxn], f[4*maxn], madd[4*maxn], mmul[4*maxn];
int n, m, p;

inline void buildTree(int k, int l, int r) { // k l r 分别是当前处理节点的下标 当前区间的左端点 当前区间的右端点 下同
    madd[k] = 0; mmul[k] = 1;
    if(l == r) { f[k] = a[l]; return; }
    int m = (l+r) >> 1;
    buildTree(lc, l, m);
    buildTree(rc, m+1, r);
    f[k] = (f[lc] + f[rc])%p;
}

inline void pushdown(int k, int l, int r) {
    int m = (l+r) >> 1;
    f[lc] = (f[lc]*mmul[k] + madd[k]*(m-l+1))%p;
    f[rc] = (f[rc]*mmul[k] + madd[k]*(r-m))%p;

    mmul[lc] = (mmul[lc]*mmul[k]) % p;
    mmul[rc] = (mmul[rc]*mmul[k]) % p;

    madd[lc] = (madd[lc]*mmul[k] + madd[k]) % p;
    madd[rc] = (madd[rc]*mmul[k] + madd[k]) % p;

    mmul[k] = 1;
    madd[k] = 0;
}

inline void add(int k, int l, int r, int x, int y, ll z) {
    if(l == x && r == y) {
        madd[k] = (madd[k] + z) % p;
        f[k] = (f[k] + z*(r-l+1)) % p;
        return;
    }
    pushdown(k, l, r);

    int m = (l+r) >> 1;
    if(y <= m) {
        add(lc, l, m, x, y, z);
    } else if(x > m) {
        add(rc, m+1, r, x, y, z);
    } else {
        add(lc, l, m, x, m, z);
        add(rc, m+1, r, m+1, y, z);
    }
    f[k] = (f[lc] + f[rc]) % p;
}

inline void mul(int k, int l, int r, int x, int y, ll z) {
    if(l == x && r == y) {
        madd[k] = (madd[k]*z) % p;
        mmul[k] = (mmul[k]*z) % p;
        f[k] = (f[k] * z) % p;
        return;
    }
    pushdown(k, l, r);
    int m = (l+r) >> 1;
    if(y <= m) {
        mul(lc, l, m, x, y, z);
    } else if(x > m) {
        mul(rc, m+1, r, x, y, z);
    } else {
        mul(lc, l, m, x, m, z);
        mul(rc, m+1, r, m+1, y, z);
    }
    f[k] = (f[lc] + f[rc]) % p;
}

inline ll query(int k, int l, int r, int x, int y) {
    if(l == x && r == y) {
        return f[k];
    }
    pushdown(k, l, r);
    int m = (l+r) >> 1;
    if(y <= m) {
        return query(lc, l, m, x, y);
    } else if(x > m) {
        return query(rc, m+1, r, x, y);
    } else {
        return query(lc, l, m, x, m) + query(rc, m+1, r, m+1, y);
    }
}

int main(void)
{
    // freopen("in.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
    }
    buildTree(1, 1, n);
    int x, y, op;
    ll k;
    while(m--) {
        scanf("%d", &op);
        if(op == 1) {
            scanf("%d%d%lld", &x, &y, &k);
            mul(1, 1, n, x, y, k);
        } else if(op == 2) {
            scanf("%d%d%lld", &x, &y, &k);
            add(1, 1, n, x, y, k);
        } else {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y)%p);
        }
    }
    return 0;
}

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116