Fork me on GitHub

分块 学习笔记

模板及讲解
主体思想是把序列分块每块长为$\sqrt n$,然后进行处理(一般是考虑1.处理不完整块2.处理完整块3.预处理的三种情况)。
分块的调试检测技巧:可以生成一些大数据,然后用两份分块大小不同的代码来对拍,还可以根据运行时间尝试调整分块大小,减小常数。

(以下文字部分转与hzwer的博客)


1 区间加法,单点查询(知识点:lazy标记)
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间加法,单点查值。Luogu 3368
解法:把原序列分块,我们把每$\sqrt n$个元素分为一块,然后就能得到$n / \sqrt n = \sqrt n$个块。我们给每个块设置一个加法标记(就是记录这个块中元素一起加了多少),每次操作对每个整块直接$O(1)$标记,而不完整的块由于元素比较少,暴力修改元素的值。每次询问时返回元素的值加上其所在块的加法标记。每次区间加的操作复杂度为$O(\sqrt n + \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
//由于luogu题目数据范围大,无法承受sprt(n)*m的复杂度,所以本程序只有70分
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 500000 + 5;
int n, m, ai[MAXN];//输入数组
int totblo, lazy[MAXN], bl[MAXN];//每块大小(sqrt(n)),lazy标记,每个数属于哪个块
void add(int x, int y, int k) {
for (int i = x; i <= min(y, bl[x] * totblo); i++) ai[i] += k;//左边的块
if (bl[x] != bl[y]) for (int i = (bl[y] - 1) * totblo + 1; i <= y; i++) ai[i] += k;//右边的块,记得有可能[x,y]只在一个块中的情况
for (int i = bl[x] + 1; i <= bl[y] - 1; i++) lazy[i] += k;//中间整块只更新lazy
}
void clean() {}
void solve() {
clean();
totblo = sqrt(n);
for (int i = 1; i <= n; i++) bl[i] = (i - 1) / totblo + 1;//随便推堆公式就能出来
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]);
while (m--) {
int opt; scanf("%d", &opt);
if (opt == 1) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
add(x, y, k);
} else if (opt == 2) {
int x;
scanf("%d", &x);
printf("%d\n", ai[x] + lazy[bl[x]]);//原数加上lazy标记值
}
}
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

扩展1: 区间加法,区间查询
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间加法,区间查询。
解法:还是按照上面的方法,但是要记录一个块的总元素和。很好维护,处理不完整块的时候就直接加就行;完整块直接按照块大小乘以增加量即可。代码略去。
扩展2: 区间乘法,单点查询/区间查询
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间乘法,单点查询/区间查询。
解法:和以上两种方法类似,不再做解释。


2 区间加法,查询区间小于/大于某数的总个数(知识点:块中套数据结构/STL等)
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间加法,区间查询区间小于/大于某数的总个数Luogu 2801
解法:思路是将序列分成$\sqrt n$个块,然后每个块排序,每次查询非整块暴力处理,整块二分。
预处理:把序列分成$\sqrt n$个块,然后分别排序
修改:非整块直接暴力修改;整块修改lazy值即可。但是非整块修改会影响这个块的顺序,而整块不会,所以非整块要重新排序。
查询:非整块直接暴力统计;整块二分即可,记得带上lazy值即可
注意:totblo只是块长,bl[n]才是总块数

这里用vector来存块的排序

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 1000000 + 5, MAXK = 1000 + 5;
LL n, Q, ai[MAXN], totblo, bl[MAXN], lazy[MAXK];
//输入的n,Q,序列ai, 总块数totblo, 每个数属于哪个块,lazy标记
vector<LL> vec_sortedBlo[MAXK];//每个块的排序后的有序区间
void add(LL x, LL y, LL c) {
for (LL i = x; i <= min(y, totblo * bl[x]); i++) ai[i] += c;
vec_sortedBlo[bl[x]].clear();
for (LL i = totblo * (bl[x] - 1) + 1; i <= totblo * bl[x]; i++) vec_sortedBlo[bl[x]].push_back(ai[i] += lazy[bl[x]]);
lazy[bl[x]] = 0;
sort(vec_sortedBlo[bl[x]].begin(), vec_sortedBlo[bl[x]].end());
//处理非整块(前)
if (bl[x] != bl[y]) {
for (LL i = (bl[y] - 1) * totblo + 1; i <= y; i++) ai[i] += c;
vec_sortedBlo[bl[y]].clear();
for (LL i = (bl[y] - 1) * totblo + 1; i <= bl[y] * totblo; i++) vec_sortedBlo[bl[y]].push_back(ai[i] += lazy[bl[y]]);
lazy[bl[y]] = 0;
sort(vec_sortedBlo[bl[y]].begin(), vec_sortedBlo[bl[y]].end());
}//处理非整块(后)
for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) lazy[i] += c;//处理整块
}
LL query(LL x, LL y, LL c) {
LL ret = 0;
for (LL i = x; i <= min(y, totblo * bl[x]); i++) if (ai[i] + lazy[bl[x]] >= c) ret++;
if (bl[x] != bl[y]) for (LL i = (bl[y] - 1) * totblo + 1; i <= y; i++) if (ai[i] + lazy[bl[y]] >= c) ret++;
//处理非整块
for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) {
//LL les = lower_bound(vec_sortedBlo[i].begin(), vec_sortedBlo[i].end(), c - lazy[i]) - vec_sortedBlo[i].begin();
LL ans = -1, l = 0, r = vec_sortedBlo[i].size();
while (l < r) {
LL mid = (l + r) >> 1;
if (lazy[i] + vec_sortedBlo[i][mid] < c) ans = mid, l = mid + 1; else r = mid;
}
ret += (LL)vec_sortedBlo[i].size() - ans - 1;
}//处理整块
return ret;
}
void clean() {
ms(bl, 0);
}
void solve() {
clean();
totblo = sqrt(n);
for (LL i = 1; i <= n; i++) bl[i] = (i - 1) / totblo + 1;
for (LL i = 1; i <= n; i++) {
scanf("%lld", &ai[i]);
vec_sortedBlo[bl[i]].push_back(ai[i]);
}
for (LL i = 1; i <= bl[n]; i++) sort(vec_sortedBlo[i].begin(), vec_sortedBlo[i].end());//预处理,排序。totblo只是块长,bl[n]才是总块数
char ch[10];
while (Q--) {
scanf("%s", ch);
if (ch[0] == 'M') {
LL l, r, w;
scanf("%lld%lld%lld", &l, &r, &w);
add(l, r, w);
} else {
LL l, r, c;
scanf("%lld%lld%lld", &l, &r, &c);
printf("%lld\n", query(l, r, c));
}
}
}
int main() {
scanf("%lld%lld", &n, &Q), solve();
return 0;
}

扩展1: 区间加法,区间添加/删除元素/求前驱/后继
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间加法,区间添加/删除元素/求前驱/后继
解:可以和上面的做法一样,不用vector而是使用set即可


3 区间开方,区间求值(知识点:块中标记优化)
给出一个长为$n$的数列,以及$m$个操作,操作涉及区间开方,区间求值SPOJ GSS4
解:非整块还是暴力更新。由于一个数sqrt很少次数变为0或1,因为一个块的开方和不能直接得到,那么只能是如果一个块全是1或0,标记这个块不再处理,否则无论是整块还是非整块都暴力更新。每个数更新的次数非常小。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 100000 + 5, MAXK = 400 + 5;
LL n, Q, totblo, bl[MAXN], ai[MAXN];
//输入n,Q,块的大小,每个元素属于的块,序列ai
LL sum[MAXK], mark[MAXK];
//块元素和,标记(是否都为1或0)
void solveSqrt(LL x) {//处理
if (mark[x]) return ;
int flag = true;
for (LL i = (x - 1) * totblo + 1; i <= x * totblo; i++) {
if (ai[i] != 0 || ai[i] != 1) {
sum[x] -= ai[i], ai[i] = sqrt(ai[i]), sum[x] += ai[i];
if (ai[i] != 0 && ai[i] != 1) flag = false;
}
}
if (flag) mark[x] = 1;//标记
}
void update(LL x, LL y) {
for (LL i = x; i <= min(y, totblo * bl[x]); i++) sum[bl[x]] -= ai[i], ai[i] = sqrt(ai[i]), sum[bl[x]] += ai[i];
if (bl[x] != bl[y]) for (LL i = totblo * (bl[y] - 1) + 1; i <= y; i++) sum[bl[y]] -= ai[i], ai[i] = sqrt(ai[i]), sum[bl[y]] += ai[i];
for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) solveSqrt(i);
}
LL query(LL x, LL y) {
LL ret = 0;
for (LL i = x; i <= min(y, totblo * bl[x]); i++) ret += ai[i];
if (bl[x] != bl[y]) for (LL i = totblo * (bl[y] - 1) + 1; i <= y; i++) ret += ai[i];
for (LL i = bl[x] + 1; i <= bl[y] - 1; i++) ret += sum[i];
return ret;
}
void clean() {
ms(sum, 0), ms(mark, 0);
}
void solve() {
clean();
totblo = sqrt(n);
for (LL i = 1; i <= n; i++) {
scanf("%lld", &ai[i]);
bl[i] = (i - 1) / totblo + 1, sum[bl[i]] += ai[i];
}
scanf("%lld", &Q);
while (Q--) {
LL x, l, r;
scanf("%lld%lld%lld", &x, &l, &r);
if (l > r) swap(l, r);
if (x == 1) {
printf("%lld\n", query(l, r));
} else {
update(l, r);
}
}
}
int main() {
LL kase = 0;
while (scanf("%lld", &n) == 1) printf("Case #%lld:\n", ++kase), solve(), printf("\n");
return 0;
}

------ 本文结束 ------