分块 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$，则原式变为了：

即将乘法标记乘上 $c$，同时也将累加标记加上 $c$。

对于区间加，如果加上了一个数 $c$，则原式变为了：

即不对乘法标记进行修改，只将加法标记加上一个 $c$。

对于零散块，会发现，如果没有将标记下传而直接修改实际值是错误的。例如，对于一个值 $x$，如果不下传标记而直接区间乘 $c$ 就会变为：

而区间加 $c$ 就会变为：

因此，对于零散块而言，需要将标记下传到块内的每一个值。

最后说一下，记得及时取模。

代码实现

分块 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#