一：分块
分块的思想就是通过合适的划分，将一部分信息预处理并保存下来，用空间来换取时间，其实分块是“优化”的暴力，效率比不上树状数组和线段树，但它更通用和容易实现。
二：例题1
给定一个长度为N(N ≤ 10^5)的数列A，然后有M(M ≤ 10^5)个操作指令。
操作1：格式：1 x y k 含义：将区间[x, y]上的每一个数都加上k
操作2：格式：2 x y 含义：输出区间[x, y]内每个数的和
Luogu P3372
这道题用线段树和树状数组都可以很优秀的通过，但我们用这道题来练一下分块
分析：
我们先将数列A分成若干个不超过 ⌊ √n ⌋ (下取整)的段，其中第i段的左端点为(i - 1)⌊ √n ⌋+1，右端点为min(i*⌊ √n ⌋, n)，例如当n = 10的时候，我们分成4块
我们可以先定义数字sum[i]，表示第 i 块的区间和，定义add[i]表示第 i 段的“增量标记”(下面细讲)，初始值为0。
1. 对于指令 1 x y k
(1).若x， y都在第 i 块内，则选择暴力更新，把A[x], A[x+1],......A[y-1], A[y]都加上k，同时将sun[i] 更新 为 sum[i] + (y - x + 1) * k
(2). 否则，设x在第p块， y在第q块
①：对于i∈[p+1, q-1], i是一个整块，所以直接add[i] += k，表示第 i 块都加上了k。(优于暴力更新)
②：对于p、q所在不足一整块的，类似于(1)进行暴力更新
2.对于指令 2 x y
(1).若x， y都在第i块内，则(A[x] + A[x+1] + ...... + A[y-1] + A[y]) + add[i] * (y - x + 1)就是答案
(2).否则设x在第p块， y在第q块， 令Ans = 0；
①：对于i∈[p+1, q-1], i是一个整块，Ans += sum[i] + add[i] * len[i];// len[i] 是第i块的长度
②：对于p、q所在不足一整块的，类似于(1)进行计算
对于t， 我们令 t = ⌊ √n ⌋， len = n / t，由于n不一定是完全平方数，所以就要新开一块的操作(Code中会说明)。由于块长块数都近似于O(√n)，所以时间复杂度为O((n + m) * √n)
Code:
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 typedef
long long LL;
5 const int maxn = 1e5 +
10;
6
7 // 分块求解 O((n+m) * √n)
8
9 LL Read();
10
11 LL n, m, t;
12 LL val[maxn], sum[maxn], add[maxn];
13 int L[maxn], R[maxn], pos[maxn];
14
15 inline
void change(
int l,
int r, LL x) {
16 int p = pos[l], q = pos[r];
// l r所在那一块
17 if(p == q) {
// 在同一块
18 for(
int i=l; i<=r; i++) val[i] += x;
// 直接更新
19 sum[p] += x * (r - l +
1);
// 更新本块的和
20 }
21 else {
// 不在同一块
22 for(
int i=p+
1; i<=q-
1; ++i) add[i] += x;
// p ~ q之间的整块
23 for(
int i=l; i<=R[p]; ++i) val[i] += x;
// 更新 p所在的非整块
24 sum[p] += x * (R[p] - l +
1);
// 更新sum
25 for(
int i=L[q]; i<=r; ++i) val[i] += x;
//更新 q所在的非整块
26 sum[q] += x * (r - L[q] +
1);
// 更新sum
27 }
28 }
29
30 inline LL ask(
int l,
int r) {
31 int p = pos[l], q =
pos[r];
32 LL Ans =
0;
33 if(p == q) {
// 在同一块
34 for(
int i=l; i<=r; ++i) Ans += val[i];
// 暴力求和
35 Ans += add[p] * (r - l +
1);
// 加上此块总共加的
36 }
37 else {
38 for(
int i=p+
1; i<=q-
1; ++i)
// 加上pq所在块之间的整块
39 Ans += sum[i] + add[i] * (R[i] - L[i] +
1);
// 加上sum和此块总共加的
40 for(
int i=l; i<=R[p]; ++i) Ans += val[i];
//加上p所在块的一些元素
41 Ans += add[p] * (R[p] - l +
1);
42 for(
int i=L[q]; i<=r; ++i) Ans += val[i];
//加上p所在块的一些元素
43
44 Ans += add[q] * (r - L[q] +
1);
45 }
46 return Ans;
47 }
48
49 int main() {
50 n = Read(), m =
Read();
51 for(
int i=
1; i<=n; ++i) val[i] =
Read();
52
53 // 分块
54 t =
sqrt(n);
55 for(
int i=
1; i<=t; ++
i) {
56 L[i] = (i-
1) * t +
1;
// 第i块的左断电
57 R[i] = i * t;
// 第i块的右端点
58 }
59 if(R[t] < n) {
// 没有分完，
60 t++;
// 新加一组
61 L[t] = R[t-
1]+
1;
// 新的一组左端点为上一组右端点的下一个
62 R[t] = n;
// 右端点为n
63 }
64
65 //预处理
66 for(
int i=
1; i<=t; ++i) {
// 枚举每一块 开始预处理
67 for(
int j=L[i]; j<=R[i]; ++
j) {
68 pos[j] = i;
// 记录每一个元素
69 sum[i] += val[j];
// 计算每一块的和
70 }
71 }
72
73 // solve
74 while(m --
) {
75 int f, x, y; scanf(
"%d%d%d", &f, &x, &
y);
76 if(f ==
1) {
//
77 LL z =
Read();
78 change(x, y, z);
79 }
80 else {
81 //printf("%lld %lld\n", x, y);
82 LL Ans =
ask(x, y);
83 printf(
"%lld\n", Ans);
84 }
85 }
86 return 0;
87 }
88 // 快读
89 inline LL Read() {
90 LL x =
0, f =
1;
char ch =
getchar();
91 while(!isdigit(ch)) {
if(ch ==
'-') f = -
1; ch =
getchar(); }
92 while(isdigit(ch)) { x = x *
10 + (ch-
48), ch =
getchar(); }
93 return x*
f;
94 }
View Code
三：例题2
Luogu P3396 哈希冲突
众所周知，模数的hash会产生冲突。例如，如果模的数p=7，那么4和11便冲突了。
B君对hash冲突很感兴趣。他会给出一个正整数序列value[]。
自然，B君会把这些数据存进hash池。第value[k]会被存进(k%p)这个池。这样就能造成很多冲突。
B君会给定许多个p和x，询问在模p时，x这个池内数的总和。
另外，B君会随时更改value[k]。每次更改立即生效。
保证1<=p<n1<=p<n.
样例输入：
10 5
1 2 3 4 5 6 7 8 9 10
A 2 1C 1 20A 3 1C 5 1A 5 0
样例输出：
25
41
11
样例解释：
A 2 1的答案是：1 + 3 + 5 + 7 + 9 = 25
C 1 20后：20 2 3 4 5 6 7 8 9 10
A 3 1的答案是：20 + 4 + 7 + 10 = 41
C 5 1后：20 2 3 4 1 6 7 8 9 10
A 5 0的答案是：1 + 10 = 11
分析：
我们可以枚举从1到⌊ √n ⌋的模数，进行 n * ⌊ √n ⌋的暴力预处理，对于p∈[1, ⌊ √n ⌋]的询问我们可以进行O(1)的回答
具体看代码注释：
Code：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int Read();
5
6 int n, m, val[
150010];
7 int t, sum[
400][
150010];
8 // sum(i, j) 当模数为 i 时，余数为 j 的和
9 // sqrt(n) ≈388
10
11 // 更新 val[pos] 的值
12 inline
void change(
int pos,
int x) {
13 // 枚举模数，∵每一个值更改后， 对不同的模数都有影响
14 // sum(i, pos%i) 减去原来的数字，加上更改的数字
15 for(
int i=
1; i<=t; ++i) sum[i][pos%i] = sum[i][pos%i] - val[pos] +
x;
16 val[pos] = x;
// 更新 pos 上的数字
17 }
18
19 // 对于模数 p 求出余数为 x 的元素和
20 inline
long long ask(
int p,
int x) {
21 long long s =
0;
22 if(p <= t) s = sum[p][x];
// ∵我们已经枚举了1~t的模数 ∴可以直接输出
23 else {
// 模数 p 大于t
24 for(
int i=x; i<=n; i+=
p)
25 s +=
val[i];
26 }
27 return s;
28 }
29
30 int main() {
31 n = Read(), m =
Read();
32 for(
int i=
1; i<=n; ++i) val[i] =
Read();
33 // 预处理
34 t =
sqrt(n);
35 for(
int j=
1; j<=n; ++j)
// 枚举位置
36 for(
int i=
1; i<=t; ++i)
// 枚举模数 p
37 sum[i][j%i] +=
val[j];
38 // 询问
39 while(m --
) {
40 char ch[
5]; scanf(
"%s", ch);
41 int x = Read(), y =
Read();
42 if(ch[
0] ==
'A') {
43 long long Ans =
ask(x, y);
44 printf(
"%lld\n", Ans);
45 }
46 else change(x, y);
47 }
48 return 0;
49 }
50
51 inline
int Read() {
52 int x=
0, f=
1;
char ch =
getchar();
53 while(!isdigit(ch)) {
if(ch ==
'-') f = -
1; ch =
getchar(); }
54 while(isdigit(ch)) { x = x *
10 + (ch-
48), ch =
getchar(); }
55 return x*
f;
56 }
View Code
转载于:https://www.cnblogs.com/Marginalin/p/9777061.html
相关资源：垃圾分类数据集及代码
