首页 程序设计 数据结构

# 【模板】线段树

# 题目大意

如题，已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 xx
  • 将某区间每一个数加上 xx
  • 求出某区间每一个数的和（对 mm 取模）

# 数据范围

对于 30%30\% 的数据：n≤8n \le 8，q≤10q \le 10
对于 70%70\% 的数据：n≤103n \le 10^3，q≤104q \le 10^4
对于 100%100\% 的数据：1≤n≤1051 \le n \le 10^5，1≤q≤1051 \le q \le 10^5
除样例外，m=571373m = 571373

# 题解

C++
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
const int N = 1e6 + 10;

int n, m, MOD, a[N];

struct STree {
    int sum, add, mul;
    int l, r;
} s[N * 4];

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

void push_down(int pos) { //pushdown的维护
	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_tree(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_tree(pos << 1, l, mid), build_tree(pos << 1 | 1, mid + 1, r);
	update(pos);
	return;
}

void Mul(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;
	}
	
	push_down(pos);

	int mid = (s[pos].l + s[pos].r) >> 1;
    
	if (x <= mid)
        Mul(pos << 1, x, y, k);
    if (y > mid)
        Mul(pos << 1 | 1, x, y, k);

    update(pos);
}

void Add(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;
	}
	
	push_down(pos);
	
    int mid = (s[pos].l + s[pos].r) >> 1;
	
    if (x <= mid)
        Add(pos << 1, x, y, k);
    if (y > mid)
        Add(pos << 1 | 1, x, y, k);

    update(pos);
}

int getRange(int pos, int x, int y) {
	if (x <= s[pos].l && s[pos].r <= y)
		return s[pos].sum;
	
	push_down(pos);
    
	int val = 0, mid = (s[pos].l + s[pos].r) >> 1;

	if (x <= mid)
        val = (val + getRange(pos << 1, x, y)) % MOD;
    if (y > mid)
        val = (val + getRange(pos << 1 | 1, x, y)) % MOD;

    return val;
}


void solve () {
    cin >> n >> m >> MOD;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    build_tree(1, 1, n);

    for (int i = 1, op, x, y, k; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 1) 
            cin >> k, Mul(1, x, y, k);
        else if (op == 2)
            cin >> k, Add(1, x, y, k);
        else
            cout << getRange(1, x, y) << endl;
    }
}