写在最前
发现文章被吃掉了好多，先重写一篇分块吧
众所周知某大佬 （Dickfuck） 说过这么一句话：
当你不会写线段树的时候，分块是你的救世主；当你学会线段树之后，分块是你的白月光。
所以我是分块的勾！
核心思想
分块的核心思想其实很简单：将序列分成若干块，对整块进行整体处理，对零散的部分进行暴力处理。
那么具体分多少块呢，不妨分析一下复杂度：
- 假设我们序列长为 $n$，块长为 $m$
- 查询操作：
- 对于整块，我们需要枚举每一个块，复杂度即为 $O(\frac{n}{m})$
- 对于零散的部分，我们暴力枚举，因为块长为 $m$，所以复杂度即为 $O(m)$
- 修改同理
- 那么整体最坏复杂度即为 $O(\frac{n}{m}+m)$
- 根据均值不等式 $\frac{a+b}{2} \ge \sqrt{ab}$ 可知，当 $\frac{n}{m}=m$ 即 $m = \sqrt(n)$ 时，复杂度最优
故当块长为 $\sqrt{m}$ 时复杂度最优，为 $O(\sqrt(n))$
不难发现不如线段树（？
那我们为什么要用粪块呢？
虽然分块常被称为”优雅的暴力”，但它绝不仅仅是暴力那么简单。分块真正的魅力在于：
- 灵活性：可以维护很多线段树难以维护的信息
- 可扩展性：可以轻松支持各种复杂的区间操作
- 调试友好：比起线段树的递归，分块的逻辑更加直观，且不需要懒标记下传等操作
——by DeepSeek
所以当你被线段树的标记下传折磨得死去活来时，不妨试试分块（
实现
初始化
不难发现如果块长为 $m$，那么第 $i$ 个块的 $id$ 即为 (i - 1) / m + 1
1
2
3
4
5
6
7
8
9
| fenkuai(int _n, int _a[]) {
n = _n;
m = sqrt(n);
for(int i = 1; i <= n; i++) {
id[i] = (i - 1) / m + 1;
a[i] = _a[i];
sum[id[i]] += a[i];
}
}
|
区间修改
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
| void modify(int l, int r, int x) {
int L = id[l], R = id[r];
if(L == R) {
for(int i = l; i <= r; i++) {
a[i] += x;
sum[L] += x;
}
return;
}
for(int i = l; id[i] == L; i++) {
a[i] += x;
sum[L] += x;
}
for(int i = L + 1; i < R; i++) {
tag[i] += x;
sum[i] += m * x;
}
for(int i = r; id[i] == R; i--) {
a[i] += x;
sum[R] += x;
}
}
|
区间查询
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
| int query(int l, int r) {
int ans = 0;
int L = id[l], R = id[r];
if(L == R) {
ans += tag[L] * (r - l + 1);
for(int i = l; i <= r; i++)
ans += a[i];
return ans;
}
for(int i = l; id[i] == L; i++) {
ans += a[i];
ans += tag[L];
}
for(int i = L + 1; i < R; i++) {
ans += sum[i];
}
for(int i = r; id[i] == R; i--) {
ans += a[i];
ans += tag[R];
}
return ans;
}
|
完整代码
喜闻乐见封装环节
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
| class fenkuai {
int n, len;
int a[N];
int id[N];
int tag[N];
int sum[N];
public:
fenkuai(int _n, int _a[]) {
n = _n;
len = sqrt(n);
for(int i = 1; i <= n; i++) {
id[i] = (i - 1) / len + 1;
a[i] = _a[i];
sum[id[i]] += a[i];
}
}
void modify(int l, int r, int x) {
int L = id[l], R = id[r];
if(L == R) {
for(int i = l; i <= r; i++) {
a[i] += x;
sum[L] += x;
}
return ;
}
for(int i = l; id[i] == L; i++) { a[i] += x; sum[L] += x; }
for(int i = L + 1; i < R; i++) { tag[i] += x; sum[i] += len * x; }
for(int i = r; id[i] == R; i--) { a[i] += x; sum[R] += x; }
}
int query(int l, int r) {
int ans = 0;
int L = id[l], R = id[r];
if(L == R) {
ans += tag[L] * (r - l + 1);
for(int i = l; i <= r; i++)
ans += a[i];
return ans;
}
for(int i = l; id[i] == L; i++) { ans += a[i]; ans += tag[L]; }
for(int i = L + 1; i < R; i++) {ans += sum[i];}
for(int i = r; id[i] == R; i--) { ans += a[i]; ans += tag[R]; }
return ans;
}
};
|
例题
世界上没有分块解决不了的题，如果有，那就多分几块
没错这是分块题👍
首先你得会这题的线段树做法，这里不过多赘述，发现使用粪块的话不好直接对零散的部分加上标记，所以我们直接对零散的部分一整个块修改
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
| class fenkuai {
int n, m;
int a[N];
int id[N];
int tag_add[N];
int tag_mul[N];
int sum[N];
public:
fenkuai(int _n, int _a[]) {
n = _n;
m = sqrt(n);
for(int i = 1; i <= n; i++) {
id[i] = (i - 1) / m + 1;
a[i] = _a[i];
(sum[id[i]] += a[i]) %= Mod;
tag_add[i] = 0; tag_mul[i] = 1;
}
}
void modify_add(int l, int r, int x) {
int L = id[l], R = id[r];
if(L == R) {
sum[L] = 0;
for(int i = (L - 1) * m + 1; i <= L * m; i++) {
(a[i] = a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
if(l <= i && i <= r)
(a[i] += x) %= Mod;
(sum[L] += a[i]) %= Mod;
}
tag_mul[L] = 1;
tag_add[L] = 0;
return ;
}
sum[L] = 0;
for(int i = (L - 1) * m + 1; i <= L * m; i++) {
(a[i] = a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
if(l <= i && i <= r)
(a[i] += x) %= Mod;
(sum[L] += a[i]) %= Mod;
}
tag_mul[L] = 1;
tag_add[L] = 0;
for(int i = L + 1; i < R; i++) {
(sum[i] += m * x) %= Mod;
tag_add[i] += x;
}
sum[R] = 0;
for(int i = (R - 1) * m + 1; i <= R * m; i++) {
(a[i] = a[i] * tag_mul[R] % Mod + tag_add[R]) %= Mod;
if(l <= i && i <= r)
(a[i] += x) %= Mod;
(sum[R] += a[i]) %= Mod;
}
tag_mul[R] = 1;
tag_add[R] = 0;
}
void modify_mul(int l, int r, int x) {
int L = id[l], R = id[r];
if(L == R) {
sum[L] = 0;
for(int i = (L - 1) * m + 1; i <= L * m; i++) {
(a[i] = a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
if(l <= i && i <= r)
(a[i] *= x) %= Mod;
(sum[L] += a[i]) %= Mod;
}
tag_mul[L] = 1;
tag_add[L] = 0;
return ;
}
sum[L] = 0;
for(int i = (L - 1) * m + 1; i <= L * m; i++) {
(a[i] = a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
if(l <= i && i <= r)
(a[i] *= x) %= Mod;
(sum[L] += a[i]) %= Mod;
}
tag_mul[L] = 1;
tag_add[L] = 0;
for(int i = L + 1; i < R; i++) {
(sum[i] *= x) %= Mod;
(tag_add[i] *= x) %= Mod;
(tag_mul[i] *= x) %= Mod;
}
sum[R] = 0;
for(int i = (R - 1) * m + 1; i <= R * m; i++) {
(a[i] = a[i] * tag_mul[R] % Mod + tag_add[R]) %= Mod;
if(l <= i && i <= r)
(a[i] *= x) %= Mod;
(sum[R] += a[i]) %= Mod;
}
tag_mul[R] = 1;
tag_add[R] = 0;
}
int query(int l, int r) {
int ans = 0;
int L = id[l], R = id[r];
if(L == R) {
for(int i = l; i <= r; i++)
(ans += a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
return ans;
}
for(int i = l; id[i] == L; i++)
(ans += a[i] * tag_mul[L] % Mod + tag_add[L]) %= Mod;
for(int i = L + 1; i < R; i++)
(ans += sum[i]) %= Mod;
for(int i = r; id[i] == R; i--)
(ans += a[i] * tag_mul[R] % Mod + tag_add[R]) %= Mod;
return ans;
}
};
|
观察数据范围
对于 $100%$ 的数据，$1\le n,m\le 10^5$，$1\le l,r\le n$，数列中的数大于 $0$，且不超过 $10^{12}$。
发现最多开根号 $6$ 次，然后就会变成 $1$，所以我们可以直接暴力开根号，然后变成 $1$ 后直接跳过：
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
| class fenkuai {
int n, m;
int a[N];
int id[N];
int tag[N];
int sum[N];
public:
fenkuai(int _n, int _a[]) {
n = _n;
m = sqrt(n);
for(int i = 1; i <= n; i++) {
id[i] = (i - 1) / m + 1;
a[i] = _a[i];
sum[id[i]] += a[i];
tag[i] = 1;
}
}
void modify(int l, int r) {
int L = id[l], R = id[r];
if(L == R) {
for(int i = l; i <= r; i++) {
sum[L] -= a[i];
a[i] = sqrt(a[i]);
sum[L] += a[i];
}
return ;
}
if(tag[L]) {
for(int i = l; id[i] == L; i++) {
sum[L] -= a[i];
a[i] = sqrt(a[i]);
sum[L] += a[i];
}
if(sum[L] == m)
tag[L] = 0;
}
for(int i = L + 1; i < R; i++) {
if(tag[i]) {
for(int j = m * (i - 1) + 1; j <= i * m; j++) {
sum[i] -= a[j];
a[j] = sqrt(a[j]);
sum[i] += a[j];
}
if(sum[i] == m)
tag[i] = 0;
}
}
if(tag[R]) {
for(int i = r; id[i] == R; i--) {
sum[R] -= a[i];
a[i] = sqrt(a[i]);
sum[R] += a[i];
}
if(sum[R] == m)
tag[R] = 0;
}
}
int query(int l, int r) {
int ans = 0;
int L = id[l], R = id[r];
if(L == R) {
for(int i = l; i <= r; i++)
ans += a[i];
return ans;
}
for(int i = l; id[i] == L; i++)
ans += a[i];
for(int i = L + 1; i < R; i++)
ans += sum[i];
for(int i = r; id[i] == R; i--)
ans += a[i];
return ans;
}
};
|
