首页 > 笔记 > 分块算法总结

分块算法总结

又是一种神奇的暴力。

分块,顾名思义,就是把序列分成块来做。

分成块,每个块暴力,就是它的基本思路。

它能解决一类无脑更新,无脑修改区间问题。

我们先看一道例题

luogu3374

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x k 含义:将第x个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

输出样例#1:

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

这题的名字叫树状数组模版,当然是可以用树状数组做了。但是假如我不想写树状数组的话,也是可以用分块水过去的。

下面就真正讲一下分块的过程:

0.初始化

我们首先把求出块的大小

\(block = \sqrt n \)

然后求出一共有多少个块

\(num = n \div block \)

再求出每一个块的左右端点

\(l[i] = (i-1) \times block + 1\)

\(r[i] = i \times block\)

最后求一下每个节点属于哪个块

\( belong[i] = (i-1) \div block + 1\)

然后就初始化完了(有可能还要维护一下别的值)

这个步骤一般所有分块都有。

 

对于这道题,还有以下的步骤。。

1.区间和

我们会得到一个区间[L,R]

假如LR在一个块内,直接暴力!

假如不在一个块内,会分成两种区间

images

一种是橘色的,一种是红色的。

橘色的直接暴力!

红色的统计一下块值就可以了

然后就出来了,是不是很简单

2.单点改

直接改一下,更新块就可以了

总程序

下一道题

luogu3368

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含2或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x 含义:输出第x个数的值

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

输出样例#1:

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

这个题和上面的差不多

初始化差不多

两个操作

1.单点查询

直接输出,O(1)

2.区间加

对于每个块,加上一个mark,假如要用这个块的话,先把mark加上,再操作。

注意细节

代码

第三道例题

luogu3372

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

输出包含若干行整数,即为所有操作2的结果。

输入输出样例

输入样例#1:

输出样例#1:

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

其实就是前两个题结合一下

还有一道

luogu3373

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数加上x

2.将某区间每一个数乘上x

3.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k

操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k

操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果

输出格式:

输出包含若干行整数,即为所有操作3的结果。

输入输出样例

输入样例#1:

输出样例#1:

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=8,M<=10

对于70%的数据:N<=1000,M<=10000

对于100%的数据:N<=100000,M<=100000

这题就比较蛋疼了,但是可以想一下线段树的mark,还是能写一写的

可惜被卡常了,无限70

【复杂度明明是过的

附一个生成器

下面讲一道真正的分块题。

luogu2801

题目描述

教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。

每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)

CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。

WD巨懒,于是他把这个回答的任务交给了你。

输入输出格式

输入格式:

第1行为两个整数N、Q。Q为问题数与教主的施法数总和。

第2行有N个正整数,第i个数代表第i个英雄的身高。

第3到第Q+2行每行有一个操作:

(1) 若第一个字母为“M”,则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。

(2) 若第一个字母为“A”,则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。

输出格式:

对每个“A”询问输出一行,仅含一个整数,表示闭区间 [L, R] 内身高大于等于C的英雄数。

输入输出样例

输入样例#1:

输出样例#1:

说明

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5,此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6,此时[1, 5]间有3个英雄的身高大于等于4。

【数据范围】

对30%的数据,N≤1000,Q≤1000。

对100%的数据,N≤1000000,Q≤3000,1≤W≤1000,1≤C≤1,000,000,000。

 

这题一眼是主席树啊,但是数据范围太zz了【好像主席树随便什么数据都能卡了

于是,我们开始暴力分块

该怎么维护这个分块呢

时刻不要忘了,分块就是暴力。

使每个块内有序,查找时二分,好像不错。

怎么保持有序?

每个块暴力sort!

更新如何保持有序

暴力sort!

明确这几点就可以肝了

最后一道题

分块+莫队

bzoj3809

3809: Gty的二逼妹子序列

Time Limit: 80 Sec Memory Limit: 28 MB
Submit: 1648 Solved: 489

Description

Autumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。
对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便,我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),对于m(1<=m<=1000000)次询问“l,r,a,b”,每次输出sl…sr中,权值∈[a,b]的权值的种类数。
Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1…sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
Output

对每个询问,单独输出一行,表示sl…sr中权值∈[a,b]的权值的种类数。

Sample Input

10 10

4 4 5 1 4 1 5 1 2 1

5 9 1 2

3 4 7 9

4 4 2 5

2 3 4 7

5 10 4 4

3 9 1 1

1 4 5 9

8 9 3 3

2 2 1 6

8 9 1 4

Sample Output

2

0

0

2

1

1

1

0

1

2

HINT

样例的部分解释:
5 9 1 2

子序列为4 1 5 1 2

在[1,2]里的权值有1,1,2,有2种,因此答案为2。
3 4 7 9

子序列为5 1

在[7,9]里的权值有5,有1种,因此答案为1。
4 4 2 5

子序列为1

没有权值在[2,5]中的,因此答案为0。
2 3 4 7

子序列为4 5

权值在[4,7]中的有4,5,因此答案为2。
建议使用输入/输出优化。

 

这题就非常的有趣了

需要对权值分块,对序列莫队

对序列莫队比较好理解,对权值就相当于分块就是维护一个桶,每次查询桶中[l,r]的元素数量。

祝AC


1 COMMENT

  1. 蒟蒻zht2017-05-18 上午7:43

    %%%分块大佬

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×