洛谷 P3373 【模板】线段树 2 题解

发表于 | 分类于 | | 热度: ℃

Description

给定一个长度为 $n$ 的数列和 $m$ 个操作，支持区间加法、区间乘法、区间求值。

数据范围：$n≤100000$ , $m≤100000$

Solution

主要注意优先级问题。每次更改的时候，加法标记都要乘以乘法标记。$push_down$ 的时候加法标记还要乘以乘法标记。

Code

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
#include <iostream>
#include <cstdio>
#define int long long
#define re register
#define mid ((l + r) / 2)
using namespace std;

const int N = 500000;
int n, m, p, opt, x, y, k;
int a[N], sum[N], mul[N], add[N];

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

void push_up(int x) { sum[x] = (sum[x * 2] + sum[x * 2 + 1]) % p; }

void push_down(int x, int l, int r)
{
    mul[x * 2] = (mul[x * 2] * mul[x]) % p;
    mul[x * 2 + 1] = (mul[x * 2 + 1] * mul[x]) % p;
    add[x * 2] = (add[x * 2] * mul[x] + add[x]) % p;
    add[x * 2 + 1] = (add[x * 2 + 1] * mul[x] + add[x]) % p;
    sum[x * 2] = (sum[x * 2] * mul[x] + add[x] * (mid - l + 1)) % p;
    sum[x * 2 + 1] = (sum[x * 2 + 1] * mul[x] + add[x] * (r - mid)) % p;
    mul[x] = 1, add[x] = 0;
    push_up(x);
}

void build(int x, int l, int r)
{
    mul[x] = 1, add[x] = 0;
    if(l == r)
    {
        sum[x] = a[l];
        return ;
    }
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    push_up(x);
}

void upd_mul(int x, int l, int r, int stdl, int stdr, int k)
{
    if(stdl <= l && stdr >= r)
    {
        mul[x] = (mul[x] * k) % p, add[x] = (add[x] * k) % p;
        sum[x] = (sum[x] * k) % p;
        return ;
    }
    if(stdl > r || stdr < l) return ;
    push_down(x, l, r);
    upd_mul(x * 2, l, mid, stdl, stdr, k);
    upd_mul(x * 2 + 1, mid + 1, r, stdl, stdr, k);
    push_up(x);
}

void upd_add(int x, int l, int r, int stdl, int stdr, int k)
{
    if(stdl <= l && stdr >= r)
    {
        add[x] = (add[x] + k) % p;
        sum[x] = (sum[x] + (r - l + 1) * k);
        return ;
    }
    if(stdl > r || stdr < l) return ;
    push_down(x, l, r);
    upd_add(x * 2, l, mid, stdl, stdr, k);
    upd_add(x * 2 + 1, mid + 1, r, stdl, stdr, k);
    push_up(x);
}

int query(int x, int l, int r, int stdl, int stdr)
{
    if(stdl <= l && stdr >= r) return sum[x] % p;
    if(stdl > r || stdr < l) return 0;
    push_down(x, l, r);
    return (query(x * 2, l, mid, stdl, stdr) + query(x * 2 + 1, mid + 1, r, stdl, stdr)) % p;
    push_up(x);
}

signed main()
{
    n = read(), m = read(), p = read();
    for(re int i = 1; i <= n; i++) a[i] = read();
    build(1, 1, n);
    for(re int i = 1; i <= m; i++)
    {
        opt = read();
        if(opt == 1)
        {
            x = read(), y = read(), k = read();
            upd_mul(1, 1, n, x, y, k);
        }
        if(opt == 2)
        {
            x = read(), y = read(), k = read();
            upd_add(1, 1, n, x, y, k);
        }
        if(opt == 3)
        {
            x = read(), y = read();
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}