分块
字面意思，把数据分成一块一块去处理。
比如数据存在一段一段连续的相同值时，把相同的值看作一个的"块"，从而快速跳过。
比如把要经常批量处理的数据分成一个一个的块，在批量处理时，整个被覆盖的块做整体处理，没整个覆盖的再挨个处理。
分块首先是一种思想，其次可以用一些套路代码。
作为一种思想，一些问题可以不显式的去做某种代码结构，而是灵活地将数据分块处理即可。
还有一些时候，可以将数据模式化地分块，然后处理一些区间操作与查询。
例：立方根
给定 \(q\)
个询问，每个询问给出一个正整数 \(x\)，求所有不大于\(x\)的数的立方根向下取整之和：
\(\sum_{j=1}^{x} \lfloor \sqrt[3]{j}
\rfloor\)
其中 \(\lfloor x \rfloor\) 表示对
\(x\) 向下取整。
题目按从小到大的顺序给出这些 \(x\)
分析：\(x\)范围很大，挨个枚举不大于
\(x\)
的数必超时。但"立方根向下取整"的值其实是一段一段相同的值组成的，比如\(1\sim 10\) 的立方根是 \(1,1,1,1,1,1,1,2,2,2\)，把立方根相同的一段段数看作一个又一个的"块"，块内相同的值乘以块的长度，就能大跨步计算立方根向下取整之和。
这道题又按从小到大顺序给 \(x\)，那么也不用开数组存前缀结果了，保存之前计算过的最后一块即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<cstdio>
#include<cstring>
#include<cmath>
long long cube(long long x) {
return x * x * x;
}
int main() {
long long q, x, last_3 = 0, last_3_sum = 0;
scanf("%lld", &q);
while(q--) {
scanf("%lld", &x);
for(;cube(last_3 + 1) <= x; last_3 ++) {
last_3_sum += (cube(last_3 + 1) - cube(last_3)) * last_3;
}
printf("%lld\n", last_3_sum + (x - cube(last_3) + 1) * last_3);
}
return 0;
}
|
例：开关
有 \(n\) 盏灯，初始状态均为关闭。有
\(m\)
次操作，每次操作为以下两种之一：
- 区间翻转：将区间 \([a,b]\)
内的灯状态全部翻转
- 区间查询：统计区间 \([a,b]\)
内开启的灯数量
输入
第一行：两个整数 \(n,m\)
(灯的数量和操作次数)
接下来 \(m\) 行：每行三个整数 \(c,a,b\)
- \(c=0\)：区间翻转操作
- \(c=1\)：区间查询操作
- \([a,b]\)：操作区间范围
1
2
3
4
5
6
| 4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
|
输出
对每个查询操作输出一行，表示区间内开启的灯数量
显然一个一个去操作会很慢，但不同的区间会重叠，整体操作又难处理多次重叠的地方。
分块是对挨个操作和整体操作的折衷：将数据分成特定大小的一块一块，标记好块对应的区域。
更新操作：
- \([a,b]\)
区间完整覆盖某一块时，给这一块打个标记，表示整块都异或过一次，这一块的和应该变为块大小减去上一次的和
- \([a,b]\)
区间没有完整覆盖某一块，但有交集，暴力更新这一块的每一个元素，但记得更新之前先应用曾经对整块打过的标记
查找操作：
- \([a,b]\)
区间完整覆盖某一块时，直接累加这一块的和
- \([a,b]\)
区间没有完整覆盖某一块，但有交集，暴力查询这一块的每个元素，也记得先应用曾经对整块打过的标记
假设分块的大小是 \(\sqrt{n}\)
，那么块的个数也是 \(\sqrt{n}\)。对于每个 \([a,b]\)，遍历所有块是 \(\sqrt{n}\)，至多首尾两个地方是部分覆盖，暴力处理
\(2\) 个块，每个块内部 \(\sqrt{n}\) 个元素，所以处理每个 \([a,b]\) 的复杂度从 \(O(n)\)（最坏情况）降低到 \(O(\sqrt{n})\)。
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
| #include<cstdio>
#include<cstring>
#include<cmath>
const int maxn = 2e5 + 10;
const int block_size = sqrt(maxn);
struct Block {
int l;
int tag;
int sum;
};
Block bl[block_size + 10];
int n, m, c, a, b, bn;
bool sta[maxn];
void Update(int a, int b) {
for(int i = 0; i < bn; i ++) {
int r = bl[i].l + block_size - 1;
if(bl[i].l >= a && r <= b) {
bl[i].tag ^= 1;
bl[i].sum = block_size - bl[i].sum;
} else if(bl[i].l <= a && a <= r || bl[i].l <= b && b <= r) {
bl[i].sum = 0;
for(int j = 0; j < block_size; j ++) {
sta[bl[i].l + j] ^= bl[i].tag;
if(bl[i].l + j >= a && bl[i].l + j <= b) {
sta[bl[i].l + j] ^= 1;
}
bl[i].sum += sta[bl[i].l + j];
}
bl[i].tag = 0;
}
}
}
int Query(int a, int b) {
int ans = 0;
for(int i = 0; i < bn; i ++) {
int r = bl[i].l + block_size - 1;
if(bl[i].l >= a && r <= b) {
ans += bl[i].sum;
} else if(bl[i].l <= a && a <= r || bl[i].l <= b && b <= r) {
for(int j = 0; j < block_size; j ++) {
sta[bl[i].l + j] ^= bl[i].tag;
ans += bl[i].l + j >= a && bl[i].l + j <= b ? sta[bl[i].l + j] : 0;
}
bl[i].tag = 0;
}
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
memset(bl, 0, sizeof(bl));
memset(sta, 0, sizeof(sta));
bn = 0;
for(int i = 1; i <= n; i += block_size) {
bl[bn ++].l = i;
}
while(m --) {
scanf("%d%d%d", &c, &a, &b);
if(c == 0) {
Update(a, b);
} else {
printf("%d\n", Query(a, b));
}
}
return 0;
}
|
启发
不要把分块当作处理区间问题的套路，它更是一种数据处理思想。毕竟区间数据处理有更高级的上位算法线段树，在那之后，处理这类区间问题时，并不会经常用分块。
掌握分块思想，应注重于在面对问题时，善于发现数据潜在特点，分块提升效率。
未来前瞻：数论分块