• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

分块学习笔记

开发技术 开发技术 2周前 (05-01) 8次浏览

0 前置芝士

  • 语言基础
  • 暴力

于是你就可以愉快地学习分块了~

1 基础思想

1-1 算法简介

分块,顾名思义,就是把序列分成一个一个的小块。

假设我们有一个长度为 (9) 的序列 ({1, 5, 3, 8, 4, 6, 7, 2, 9}),我们考虑将序列划分为三个小块:

分块学习笔记

那么这样划分有什么用呢?我们看到下面这道题。

1-2 例 1

loj #6277 数列分块入门 1

【题意简述】

  • 给定一个长度为 (n) 的序列,有 (n) 次操作,每次操作为区间加法或单点查值,对于每次查询操作请输出答案。
  • (n le 10^5)

【区间加法】
假设我们要对 ([3, 8]) 这个区间加上 (3),我们发现,这个区间涉及到了三个小块,其中第一块与第三块是不完整的,第二块是完整的

那么对于两端不完整的小块,我们考虑暴力修改,将每个点的值加上 (3)

对于中间完整的小块,我们可以将整个块打上一个标记,表明这个小块已经加上了 (3)

分块学习笔记

我们此时再将 ([2, 7]) 这个区间加上 (2),那么同样,两端的块暴力修改,中间的块打上标记。

分块学习笔记

另外,当区间涉及到的块小于等于 (2) 时,只有两端的块,此时暴力修改即可。

总结:在进行区间加法操作时,两端的块暴力修改,中间的块打上标记即可。


【单点查询】
假设在做完上面的修改之后,我们要查询下标为 (4) 的点的值,我们发现在上图中吗,下标为 (4) 的点的值为 (8),所以答案就是 (8)……

等等,我们貌似遗漏了这个小块的标记。标记上清清楚楚地写了这个小块加上了 (5),我们怎能视而不见?

所以说我们应该再加上此点所在块的标记,因此答案就是 (8 + 5 = 13) 了。很简单吧

总结:在进行单点查询操作时,答案就是该点的值加上所在块的标记。


【块长】
那么此时又产生了一个问题,每一个小块的块长应该定为多少呢?

对于每一次区间加法的操作,易知时间复杂度为 (O(2k + p)),其中 (k) 为每一个小块的长度, (p) 为总共有几个小块。

那么根据均值不等式,每一个小块的块长取到 (sqrt{n}) 时是最优的,于是块长就是你啦,(sqrt{n})


【代码】

#include <bits/stdc++.h>
using namespace std;

const int L = 5e4 + 5;
int n, block, opt, l, r, c, a[L], belong[L], tag[L];

void add() {
	if (belong[l] >= belong[r]-1) { //特判,如果涉及的小块小于等于两个时,直接暴力修改。
		for (int i = l; i <= r; i++)
			a[i] += c;
		return ;
	}
	
	for (int i = l; i <= belong[l]*block; i++) 
		a[i] += c; //左端小块暴力修改
	for (int i = (belong[r]-1)*block+1; i <= r; i++)
		a[i] += c; //右端小块暴力修改
	
	for (int i = belong[l]+1; i <= belong[r]-1; i++)
		tag[i] += c; //中间小块打上标记
}

void search() {
	printf("%dn", a[r]+tag[belong[r]]);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	block = sqrt(n);
	for (int i = 1; i <= n; i++)
		belong[i] = (i-1)/block + 1; //belong 数组表示每个位置属于哪个块。
		
	for (int i = 1; i <= n; i++) {
		scanf("%d %d %d %d", &opt, &l, &r, &c);
		
		if (opt == 0) add();
		else search();
	}
	
	return 0;
} 

2 例题分析

2-1 例 2

loj #6280 数列分块入门 4

【题意简述】

  • 给定一个长度为 (n) 的序列,有 (n) 次操作,每次操作为区间加法或区间求和,对于每次查询操作请输出答案。
  • (n le 5*10^4)

【思路 & 分析】

与例 1 唯一的不同点,就是这次不再是单点查询,而是区间查询。

那么既然加法操作不变,那么我们同样,两端的块暴力修改,中间的块打上标记。

对于区间查询怎么办?我们发现同样可以将区间涉及的块分为两端与中间。

对于两端的块,我们同样可以考虑暴力查询,别忘了每个数都要加上标记。

对于中间的块,我们可以先预处理出每一块的和,然后一块一块地跳,将答案加上 (sum + tag * k),其中 (sum) 表示该块的和, (tag) 表示我们可爱的标记, (k) 表示块长。

于是这道题就愉快地被我们解决了~

2-2 例 3

loj #6281 数列分块入门 5

【题意简述】

  • 给定一个长度为 (n) 的序列,有 (n) 次操作,每次操作为区间开方(向下取整)或区间求和,对于每次查询操作请输出答案。
  • (n le 5*10^4, a_i le 2^31-1)

【思路 & 分析】

依照之前做题的经验,我们应该在修改操作中给区间打上标记,可这次会出现精度的问题,例如 ({lfloorsqrt{15}rfloor}+{lfloorsqrt{15}rfloor} neq {lfloorsqrt{15+15}rfloor}),怎么办?

我们发现序列中的每一个数都在 int 范围内,而这些数最多进行 (5) 次操作就会变成 (1)(0),而之后就不会改变了,于是我们可以在前期暴力修改,然后如果一个块内全部变成了 (1)(0),就在之后的暴力修改中跳过它。

真是一道暴力的题呢

2-3 例 4

洛谷 P1438 无聊的数列

【题意简述】

  • 维护一个长度为 (n) 的序列,有 (m) 次操作,每次操作为区间加等差数列或单点查值对于每次查询操作请输出答案。
  • (n, m le 10^5)

【思路 & 分析】

此题的关键在于发现等差数列的一个性质

我们发现,两个等差数列相加后依旧是等差数列,例如 (1, 2, 3, 4, 5)(1, 3, 5, 7, 9) 相加后会变成 (2, 5, 8, 11, 14)

再次观察,我们发现相加后的等差数列首相与公差分别是之前两个数列的首相之和与公差之和

于是对于每一个小块,我们可以考虑维护这个块内等差数列的首相与公差。

那么对于修改操作,如果为中间块则首相与公差加上给定等差数列,否则暴力修改就可以啦。


程序员灯塔
转载请注明原文链接:分块学习笔记
喜欢 (0)