【分块】数列分块入门1-9 by hzwer

2016年6月18日5,44013

整理一些思路,然后我会在CH小组内出一系列的分块训练题

https://www.contesthunter.org/group/%E7%A6%8F%E5%BB%BA%E5%B8%88%E5%A4%A7%E9%99%84%E4%B8%AD

已完结

由于每道题题面太长,限于篇幅,只给出大意,具体题目见小组内赛题,代码附在文末

 

可能涉及的几个词语解释:

区间:数列中连续一段的元素

区间操作:将某个区间[a,b]的所有元素进行某种改动的操作

块:我们将数列划分成若干个不相交的区间,每个区间称为一个块

整块:在一个区间操作时,完整包含于区间的块

不完整的块:在一个区间操作时,只有部分包含于区间的块,即区间左右端点所在的两个块

分块入门 1 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间加法,单点查值。

 

这是一道能用许多数据结构优化的经典题,可以用于不同数据结构训练。

数列分块就是把数列中每m个元素打包起来,达到优化算法的目的。

 

以此题为例,如果我们把每m个元素分为一块,共有n/m块,每次区间加的操作会涉及O(n/m)个整块,以及区间两侧两个不完整的块中至多2m个元素。

我们给每个块设置一个加法标记(就是记录这个块中元素一起加了多少),每次操作对每个整块直接O(1)标记,而不完整的块由于元素比较少,暴力修改元素的值。

每次询问时返回元素的值加上其所在块的加法标记。

这样每次操作的复杂度是O(n/m)+O(m),根据均值不等式,当m取√n时总复杂度最低,为了方便,我们都默认下文的分块大小为√n。

分块入门 2 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的元素个数。

 

有了上一题的经验,我们可以发现,数列简单分块问题实际上有三项东西要我们思考:

对于每次区间操作:

1.不完整的块 的O(√n)个元素怎么处理?

2.O(√n)个 整块 怎么处理?

3.要预处理什么信息(复杂度不能超过后面的操作)?

 

我们先来思考只有询问操作的情况,不完整的块枚举统计即可;而要在每个整块内寻找小于一个值的元素数,于是我们不得不要求块内元素是有序的,这样就能使用二分法对块内查询,需要预处理时每块做一遍排序,复杂度O(nlogn),每次查询在√n个块内二分,以及暴力2√n个元素,总复杂度O(nlogn + n√nlog√n)。

可以通过均值不等式计算出更优的分块大小,就不展开讨论了

 

那么区间加怎么办呢?

套用第一题的方法,维护一个加法标记,略有区别的地方在于,不完整的块修改后可能会使得该块内数字乱序,所以头尾两个不完整块需要重新排序,复杂度分析略。

在加法标记下的询问操作,块外还是暴力,查询小于(x – 加法标记)的元素个数,块内用(x – 加法标记)作为二分的值即可。

分块入门 3 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的前驱(比其小的最大元素)。

 

n<=100000其实是为了区分暴力和一些常数较大的写法。

接着第二题的解法,其实只要把块内查询的二分稍作修改即可。

不过这题其实想表达:可以在块内维护其它结构使其更具有拓展性,比如放一个 set ,这样如果还有插入、删除元素的操作,会更加的方便。

 

分块的调试检测技巧:

可以生成一些大数据,然后用两份分块大小不同的代码来对拍,还可以根据运行时间尝试调整分块大小,减小常数。

分块入门 4 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间加法,区间求和。

 

这题的询问变成了区间上的询问,不完整的块还是暴力;而要想快速统计完整块的答案,需要维护每个块的元素和,先要预处理一下。

考虑区间修改操作,不完整的块直接改,顺便更新块的元素和;完整的块类似之前标记的做法,直接根据块的元素和所加的值计算元素和的增量。

分块入门 5 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间开方,区间求和。

 

稍作思考可以发现,开方操作比较棘手,主要是对于整块开方时,必须要知道每一个元素,才能知道他们开方后的和,也就是说,难以快速对一个块信息进行更新。

看来我们要另辟蹊径。不难发现,这题的修改就只有下取整开方,而一个数经过几次开方之后,它的值就会变成 0 或者 1。

如果每次区间开方只不涉及完整的块,意味着不超过2√n个元素,直接暴力即可。

如果涉及了一些完整的块,这些块经过几次操作以后就会都变成 0 / 1,于是我们采取一种分块优化的暴力做法,只要每个整块暴力开方后,记录一下元素是否都变成了 0 / 1,区间修改时跳过那些全为 0 / 1 的块即可。

这样每个元素至多被开方不超过4次,显然复杂度没有问题。

分块入门 6 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及单点插入,单点询问,数据随机生成。

 

先说随机数据的情况

之前提到过,如果我们块内用数组以外的数据结构,能够支持其它不一样的操作,比如此题每块内可以放一个动态的数组,每次插入时先找到位置所在的块,再暴力插入,把块内的其它元素直接向后移动一位,当然用链表也是可以的。

查询的时候类似,复杂度分析略。

 

但是这样做有个问题,如果数据不随机怎么办?

如果先在一个块有大量单点插入,这个块的大小会大大超过√n,那块内的暴力就没有复杂度保证了。

还需要引入一个操作:重新分块(重构)

每根号n次插入后,重新把数列平均分一下块,重构需要的复杂度为O(n),重构的次数为√n,所以重构的复杂度没有问题,而且保证了每个块的大小相对均衡。
当然,也可以当某个块过大时重构,或者只把这个块分成两半。

分块入门 7 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间乘法,区间加法,单点询问。

 

很显然,如果只有区间乘法,和分块入门 1 的做法没有本质区别,但要思考如何同时维护两种标记。

我们让乘法标记的优先级高于加法(如果反过来的话,新的加法标记无法处理)

若当前的一个块乘以m1后加上a1,这时进行一个乘m2的操作,则原来的标记变成m1*m2,a1*m2

若当前的一个块乘以m1后加上a1,这时进行一个加a2的操作,则原来的标记变成m1,a1+a2

分块入门 8 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及区间询问等于一个数c的元素,并将这个区间的所有元素改为c。

 

区间修改没有什么难度,这题难在区间查询比较奇怪,因为权值种类比较多,似乎没有什么好的维护方法。

模拟一些数据可以发现,询问后一整段都会被修改,几次询问后数列可能只剩下几段不同的区间了。

我们思考这样一个暴力,还是分块,维护每个分块是否只有一种权值,区间操作的时候,对于同权值的一个块就O(1)统计答案,否则暴力统计答案,并修改标记,不完整的块也暴力。

 

这样看似最差情况每次都会耗费O(n)的时间,但其实可以这样分析:

假设初始序列都是同一个值,那么查询是O(√n),如果这时进行一个区间操作,它最多破坏首尾2个块的标记,所以只能使后面的询问至多多2个块的暴力时间,所以均摊每次操作复杂度还是O(√n)。

换句话说,要想让一个操作耗费O(n)的时间,要先花费√n个操作对数列进行修改。

初始序列不同值,经过类似分析后,就可以放心的暴力啦。

分块入门 9 by hzwer

给出一个长为n的数列,以及n个操作,操作涉及询问区间的最小众数。

 

这是一道经典难题,其实可以支持修改操作,具体见陈立杰大神的区间众数解题报告。

而且不强制在线的话有很多做法,可以看我blog一道类似题目 czy的后宫3

 

bzoj2724 是道强制在线区间众数,而且题目背景写的不错,这道题的题解就贴传送门咯

程序

分块入门1:

分块入门2:

分块入门3:

分块入门4:

分块入门5:

分块入门6:

分块入门7:

分块入门8:

分块入门9: