入门分块 1-9 笔记
Cerisier
·
·
个人记录
分块 1
题目链接
操作涉及区间加法，单点查值。
这个还算比较板子的。
零散块暴力，整块加上一个 \text{tag}，但是貌似这道题里面块的值并不重要。
最后答案就是 a_x+b[bel_x].tag
代码实现
分块 2
题目链接
操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
很板子，但是调了 2 天才调出来，是整块处理的时候出错了。
题目要求我们计算小于 c^2 的数的数量，如果我们直接进行暴力从块的开始到末尾扫一遍的话，这样会很容易被卡成 \mathcal{O}(n^2) 的，所以我们考虑二分。
很显然，给出的序列未必是单调的。因此，我们每个块内都要单独储存这个块内数值的信息，然后进行排序。初始化的时候也要进行排序。
对于整块而言，修改后没有必要进行排序，因为是整个块内的值都增加 c，所以块内的值互相的大小关系没有变化，所以不需要更新。
对于零散块而言，暴力即可。对于整块而言，可以直接二分。
之所以我调了两天，就是因为处理整块的时候，第 i 个块被我认为成了是第 i 个元素，然后在进行查询块内的值的时候加上了一个 bel_i，导致错误。
简化思路就是：块内排序，查询时二分，零散块暴力。
代码实现
类似的题可以去写 P2801 教主的魔法，LOJ 这道题数据过弱，甚至纯暴力都能过。
分块 3
题目链接
操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。
我们看到比某一个数更小的最大数，很容易想到二分。整块排序，然后再用 lower_bound 找到块内第一个比 x 大的值，然后将下标 -1 就是这个块内 x 的前驱。注意这里如果 lower_bound 找到的下标为 0，则表示这个块里面没有比 x 更小的数了，continue 掉这个块即可。
然后对于零散块，暴力找到比 x 小的最大值，最后判一下答案合不合法即可。
简化思路就是：块内排序，查询时二分找下标，零散块暴力。
代码实现
分块 4
题目链接
操作涉及区间加法，区间求和。
我觉得这是除了分块 1 以外最简单的一道了，但是还是调了一段时间（主要是忘记初始化块了）。
然后对于这道题而言，每个块存储一个 \text{val} 表示这个块内之和，然后加上一个懒惰标记 \text{tag}。注意，这里的 \text{tag} 是表示块内 单个值 的懒惰标记，而不是整个块。
那么对于零散块而言，可以直接暴力求和，第 i 个数的值就是 a_i+b[\text{bel}_i].\text{tag}。然后整块的话，就是块的值再加上懒惰标记乘上块长。
然后，其实这道题的代码也可以通过分块 1。因为对于单独一个数 x，可以看成是区间 [x,x] 内的和。
代码实现
分块 5
题目链接
操作涉及区间开方，区间求和。
这道题有点思维难度。首先，你会发现一个很严重的问题：\sqrt{a}+\sqrt{b}\ne \sqrt{a+b}，不能直接用懒惰标记了。
我们很容易发现，对于一个数不断开方，会十分迅速地退化为 0 或 1。而且 0 和 1 开方都是等于他本身，再对他们进行操作就是浪费时间。
因此，我们块内需要额外储存一个当前块内最大值。只有在当前块内最大值大于 1 的时候再执行操作，否则不用管即可。注意每次操作完成后都要更新最大值。
然后洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国 和这道题一样，可以作为练习。
代码实现
分块 6
题目链接
操作涉及单点插入，单点询问，数据随机生成。
这道题我本来想用 vector 暴力做法当做对拍使得，想交一下测一下正确性，结果不小心过了。代码实现
分块以后写，还不会（
分块 7
题目链接
操作涉及区间乘法，区间加法，单点询问。
首先，我们发现查询操作很简单，不需要进行过多的考虑，但是修改操作略显繁琐。
我们修改需要维护两种操作：区间乘和区间加。我们可以在块内创建两个标记，一个是区间乘标记 \text{mul}，另一个区间加标记 \text{add}。初始的时候 \text{mul=1,add=0}。
对于区间乘，发现对于块内的一个值 x，实际的值应该是：
(x\times \text{mul})+\text{add}
但如果乘上了一个数 c，则原式变为了：
\begin{aligned}
&c(x\times \text{mul})+c\times\text{add}\\
=&(x\times (c\times\text{mul}))+c\times\text{add}
\end{aligned}
即将乘法标记乘上 c，同时也将累加标记加上 c。
对于区间加，如果加上了一个数 c，则原式变为了：
(x\times \text{mul})+\text{add}+c
即不对乘法标记进行修改，只将加法标记加上一个 c。
对于零散块，会发现，如果没有将标记下传而直接修改实际值是错误的。例如，对于一个值 x，如果不下传标记而直接区间乘 c 就会变为：
\begin{aligned}
&(x\times c)\times \text{mul}+\text{add}\\
\ne&((x\times \text{mul})+\text{add})\times c
\end{aligned}
而区间加 c 就会变为：
\begin{aligned}
&(x+c)\times\text{mul}+\text{add}\\
\ne&((x\times \text{mul})+\text{add})+c
\end{aligned}
因此，对于零散块而言，需要将标记下传到块内的每一个值。
最后说一下，记得及时取模。
代码实现
分块 8
题目链接
操作涉及区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。
先是看到有区间推平，想到了珂朵莉树，然后不小心过了。代码实现
然后这题的珂朵莉树貌似是卡不掉的，因为推平操作和查询操作绑定在了一起，推平操作一定占到了总操作数的 50\%，所以应该算是正解。
分块等会写
update 2022.5.1：放假了，终于把分块做法补上了。
观察题目，发现对于 50\% 的询问，都会将一个区间变为一个相同的数，而且，数据范围很大，所以势必会让一段区间内每个数字都相等。如果仍然暴力计算数字相等区间内的答案，那么将会花费很多时间。
这里我们可以往块内增加一个属性 \text{flag} 和 \text{tag}，其中 \text{flag} 是个 \text{bool} 变量，储存着当前块管辖的区间内是否每个值都相等，\text{tag} 是个 \text{int} 变量，储存着如果 \text{flag} 为 \text{true}，那么区间内每个值都是多少。
可以想到，对于整块而言，如果标记为 \text{true}，那么直接将答案加上块内元素数量，否则暴力；对于零散块而言，直接暴力，注意，要将块内的 \text{tag} 下传到实际的值，如果直接使用原数组内的 a_i 是错误的，因为在修改的时候是直接修改覆盖到的块的 \text{tag} 和 \text{flag}，并不会对块内实际值做出改变。
然后对于修改，零散块暴力，注意下传标记，整块改 \text{flag} 和 \text{tag}。
解决！
代码实现
分块 9