Problem’s Website
- 模板_线段树2
Solution
- 这道题可以用多种方法解决，例如线段树、树状数组，这些内容本菜鸡曾经写过，可以去我的其他Blog查看，本篇题解说一些分块做法。
- 分块是一种根号数据结构，优雅的暴力，时间复杂度为$\Theta(m \sqrt{n})$，大意就是把整个序列分成$\sqrt{n}$块，带两个标记，一个乘法标记、加法标记，每次区间修改$[x,y]$把两个元素所在的块中下传标记，修改时，如果$x,y$在同一块内，就维护区间修改，否则就把在一个块的内容区间修改，把两边剩余的块暴力修改。
- 听到上面的解释可能有点懵，我把代码中的变量解释一下，然后详解在下面的Code中。
- $sum[i]$为第$i$块的区间和。
- $l[i], r[i]$为第$i$块的左右端点。
- $pos[i]$为第i个元素在第几个块。
- $add[i]mul[i]$为加法乘法标记。
- $tot[i]$为第$i$个块的元素个数。
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
112
113
114
115
116
117
118
119
120
121
122
123
124
using namespace std;
typedef long long ll;
const int Maxn = 100000 + 10;
ll sc() {
ll xx = 0, ff = 1; char cch = gc;
while (cch < '0' || cch > '9') {
if (cch == '-') ff = -1; cch = gc;
}
while (cch >= '0' && cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
ll n, m, sq, mod;
ll a[Maxn];
ll pos[Maxn], l[400], r[400], sum[400], add[400], tot[400], mul[400];
void pushdown(ll x) { //下传标记，把x所在的块的标记更新到块内每个元素上
for(int i = l[pos[x]]; i <= r[pos[x]]; i++)
a[i] = (a[i] * mul[pos[x]] + add[pos[x]]) % mod; //更新
mul[pos[x]] = 1; add[pos[x]] = 0; //标记初始化
}
void modify1(ll x, ll y, ll num) { //乘法
pushdown(x); //先把x所在块pushdown
if(pos[x] == pos[y]) { //x,y在同一块内
for(int i = x; i <= y; i++) { //更新
sum[pos[i]] += a[i] * (num - 1);
a[i] *= num; a[i] %= mod;
}
sum[pos[x]] %= mod;
return ;
}
pushdown(y); //把y所在的块pushdown
for(int i = pos[x] + 1; i <= pos[y] - 1; i++) { //整块修改
sum[i] *= num; sum[i] %= mod;
mul[i] *= num; mul[i] %= mod;
add[i] *= num; add[i] %= mod; //注意乘法是加法标记也要维护
}
for(int i = x; i <= r[pos[x]]; i++) { //修改左边多出的块
// cout << i << " ";
sum[pos[i]] += (num - 1) * a[i];
a[i] *= num; a[i] %= mod;
}
// cout << endl;
sum[pos[x]] %= mod;
for(int i = l[pos[y]]; i <= y; i++) { //修改右边多出的块
// cout << i << " ";
sum[pos[i]] += (num - 1) * a[i];
a[i] *= num; a[i] %= mod;
}
// cout << endl;
sum[pos[y]] %= mod;
}
void modify2(ll x, ll y, ll num) { //加法，同上
pushdown(x);
if(pos[x] == pos[y]) {
for(int i = x; i <= y; i++) {
a[i] += num, sum[pos[i]] += num;
}
sum[pos[x]] %= mod;
return ;
}
pushdown(y);
for(int i = pos[x] + 1; i <= pos[y] - 1; i++) {
sum[i] += num * tot[i];
add[i] += num;
}
for(int i = x; i <= r[pos[x]]; i++) {
a[i] += num, sum[pos[i]] += num;
}
for(int i = l[pos[y]]; i <= y; i++) {
a[i] += num, sum[pos[i]] += num;
}
sum[pos[x]] %= mod; sum[pos[y]] %= mod;
}
ll query(ll x, ll y) { //区间查询，基本含义同上
ll res = 0;
if(pos[x] == pos[y]) {
for(int i = x; i <= y; i++)
res += (a[i] * mul[pos[i]] + add[pos[i]]);
return res;
}
for(int i = pos[x] + 1; i <= pos[y] - 1; i++)
res += sum[i];
for(int i = x; i <= r[pos[x]]; i++)
res += (a[i] * mul[pos[i]] + add[pos[i]]);
for(int i = l[pos[y]]; i <= y; i++)
res += (a[i] * mul[pos[i]] + add[pos[i]]);
return res % mod;
}
int main() {
n = sc(); m = sc(); mod = sc();
sq = (ll)sqrt(n);
for(int i = 1; i <= n; i++) {
a[i] = sc();
pos[i] = (i - 1) / sq + 1; //用公式计算出第i个元素在第几个块
if(!l[pos[i]]) l[pos[i]] = i; //如果左端点为标记，就标记上
r[pos[i]] = i; //不断更新右端点，到最后一定正确
tot[pos[i]]++; //元素个数++
sum[pos[i]] += a[i]; //区间和维护
mul[pos[i]] = 1; //乘法标记要初始化为1
}
while(m--) {
ll flag = sc(), x = sc(), y = sc();
if(flag == 1) {
ll num = sc();
modify1(x, y, num); //区间乘法
}
else if(flag == 2) {
ll num = sc();
modify2(x, y, num); //区间加法
}
else {
printf("%lld\n", query(x, y)); //区间求和
}
}
return 0;
}
// Coded by dy.
rp++