分块 学习笔记

分块 学习笔记

分块。这就是分块。记得同届的应该都是初一就会了吧。

自己还是很可笑。啥都不会。

分块其实是一种「思想」。就是字面意思，把整个序列按照一定长度，划分成若干个块，然后对于每个块我们去维护一些信息。

你可以认为这是一种优化的暴力。

这样的话，我们对每个块去整体考虑，这样的「整体」其实只有 \sqrt n 的级别，这样就达到了一种平衡，让时间复杂度可以承受。

P3203 [HNOI2010] 弹飞绵羊

这是分块思想的题目，注意到我们暴力跳肯定是不行的。我们考虑分块。

其实这题感觉转成树形结构是更好想的？

对于每个块，我们维护块内每个点跳出这个块的步数和位置，这个我们扫一遍就可以维护。

因为是单点修改，所以我们每次只用对一个块重构，这是 \sqrt n 的。

按照整体来看，我们最多跳 \sqrt n 个块，所以时间复杂度是 O(m \sqrt n) 的。

分块是较为灵活的，我们还是回到最简单的单点/区间加，区间/单点查询上面去。

P2357 守墓人

首先是预处理。我们要预处理块长（一般是 \sqrt n），每个块的左右端点，以及 [1,n] 每个位置属于那个块。

这个显然可以做到 O(n)。

对于每个块，我们需要维护块内所有数的和，记为 S_i。

单点修改显然是容易的，我们找到点对应的块改 S 就行。

对于区间修改，我们需要用线段树的思想，维护一个 lzy_i 表示，对于当前块而言，所有数都加了值。

所以对于区间修改，我们遇到整块，直接打标记并修改 S_i 即可，遇到散块，我们就暴力修改（这里的长度显然不超过 \sqrt n）。

对于区间查询，我们遇到整块，直接查询 S，遇到散块，那么就暴力，下放标记查询就好了。

我们这样做时间复杂度显然是 O(n \sqrt n)。

如果你用线段树的角度去看的话，维护最值也是显然的。

这就是分块最基础的应用。注意实现的时候，l,r 在同一块的情况。

不妨把他和我们的普通暴力比较。

普通暴力相当于就是认为块长为 1，把 1 看成整体，改的时候要跳 \frac{n}{1} 次，所以我们的时间复杂度是 O(n^2) 的，但是分块的块长是 \sqrt n 的，跳 \frac{n}{\sqrt n} 次。

所以一般取 \sqrt n 就能达到平衡，是优秀的。

Loj 分块 9 题

经典的训练。启动！

T1，T4，T7 都是上面讲过的类似题。

T2，T3 是一类题，讲一下 T2，很经典。

我们对每个块维护一个 vector 表示当前块，块内数排序以后的状态。

要找块内小于 x 的数的个数，我们只用在块内二分即可。

对于区间加，涉及到散块，我们就把那个块单独拎出来重构，对于整块而言，区间加不会改变相对大小关系，打标记即可。

分块体现出来的就是：把问题摊到若干块上去怎么去维护，因为一个块内数的数量只有 \sqrt n 个，来保证时间复杂度。所以我们可以灵活的维护想要的东西。

就像这里，维护排序后的状态。比较厉害。

T5：区间开方，区间求和。

这是一个结论题。我们对一个数开方，开个 10 次的样子就会变成 1 了。

所以每个块开方次数不超过 10 次，所以我们记录每个块开方次数，小于 10 次暴力，大于 10 次，块内每个数必然为 1。

T8：区间查询等于 x 数的数量，同时区间推平。

就是这个“同时”，太厉害了。

我好像只会一个 n\sqrt n \log n 的/xk。

正解是，对于每个块，我们维护块内的数是否相同，如果不同，我们暴力统计，如果相同我们直接判断。

这样为什么能保证时间复杂度呢。因为一个块查询的次数 \le 一个块内的数是不同的次数 \le n。

所以总的时间复杂度是 O(n \sqrt n)。

剩下两个题还没写。

P5309 [Ynoi2011] 初始化

第一道 Ynoi，谁知道 500ms 能跑多少啊。

观察部分分，提示我们如果 x>300，涉及的位置不多，我们直接暴力单点修改即可。

这里不能用线段树等维护，因为还要带个 \log，但是分块，就能够 O(1) 单点修改。

如果 x<300 呢？

不妨对固定的 x 考虑，显然，我们可以刻画成把原序列按照 x 长度划分块，其实就是在每个块里面的第 y 个位置 +z。

容易观察到，对于每个块而言修改的位置 \bmod x 是相同的。所以我们大可以看成一个块。

考虑查询的时候固定 x。

那么对于 [l,r] 里面的整块的贡献都是一样的，我们只用考虑散块，其实也是规约到上文的一个块里面，只用维护前缀和即可。

P10045 [CCPC 2023 北京市赛] 线段树

维护连乘？困难。应该是往推柿子的方法靠一靠。

考虑整块我们怎么做，不妨按照惯性想我们维护一个 lzy 表示加了多少数到这个块上。

比如说当前块是 \{x,y,z\}，加上了 p，那么当前块的乘积表示成 (x+p)\times (y+p) \times (z+p)。

简单展开，是 xyz+xyp+xpz+xpp+pyz+pyp+ppz+ppp。

如果我用这样的方式表示，我们不难想到，展开式的每一项其实就是在一个 () 中任选一项拼起来对吧。

所以我们把当前块里面的数和加上的数（标记）分开考虑。假设我们写成下面这张图的形式;

红色 p 是系数，x,y,z 是块内的数。

我们显然有，如果选了 a 个块内的数，那么我们就一定选了 siz-a 个系数 p 对吧。

我们专心考虑这个黑色部分。

好的，那么我们现在的一个子问题是，我要求在块内选 [1,siz] 个数，他们的乘积之和是多少。

其实这里我在想的时候的做法要用除法，是假的， 这里直接讲正解，是递推。

考虑 f_{i,j} 表示前 i 个数里面选 j 个数的答案。

显然有：

f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times a_i

但是，注意到如果我们这样去重构块的话时间是 O(n) 的承受不了。

然后这里我也没观察出来，注意到加上的数都是偶数，即 p 是偶数，说明，当我的部分超过 20 个的时候（从右往左），都是没有意义的（因为这个系数取模就是 0了）。

所以这时候我们只用 \sqrt n\times 20 的时间去重构这个块。

那么注意你选了 a 个系数，你就要选 siz-a 个块内的数，所以要设成 f_{i,j} 表示前 i 个不选 j 个的答案。

这样才能保证 j 这一维范围是 20。

有：

f_{i,j}=f_{i-1,j-1}+f_{i-1,j}\times a_i

具体的，这时候我们选的是 i-j 个，这下应该这个方程就不难理解了吧。

具体实现的时候 i 这维用倒序枚举就能够滚掉。

然后就正常分块就做完了。其实也不用卡常，加个快读就擦着过去了，懒。