LOJ 数列分块入门 9 题 做题记录

· · 个人记录

题目传送门

T1

区间加，单点查询。

板子，用 tag 数组记录每个块整体加上的值。

Code

T2

区间加，区间查询小于 x 的数的个数。

查询小于 x 的数的个数容易想到排序然后二分，因为是计数所以可以直接分块（块与块之间互不影响）。

考虑区间加，给一个块整体加上一个值不影响块内元素的值的相对顺序，所以用 tag 记录即可，对于非整块的直接暴力单点加然后对所在块重新排序即可。

查询的时候在每个块里面 lowerbound (x-tag_i) 即可。

Code

T3

区间加，区间查询 x 的前驱（小于 x 的最大值）。

和 T2 几乎一样。

Code

T4

区间加，区间求和。

板子，同 T1。

Code

T5

区间开方，区间求和。（保证 a_i\ge 0）

考虑开方操作的性质。

考虑把每个数 x 视为 2^{\lceil \log_2 x \rceil}。

一个大于 1 的数开方后的 \log_2 值一定不大于原来的 \frac{1}{2}，所以不考虑 1 和 0 的情况下，每个数最多被开方的次数大致是 \log_2\log_2 。

所以记录每个块的最大值，操作的时候如果最大值小于等于 1 直接跳过，否则就进入这个块然后暴力开方，更新最大值。

Code

T6

单点插入，单点查询。

考虑对每个块维护一个 vector，插入的时候遍历块直到 \sum size\ge x，然后就进入这个块的 vector 进行插入。查询的时候也是一样的，遍历然后访问 vector 就行了。

但是有个问题就是，可能会出现连续往同一个块里面插入很多数字的情况，然后这个块的 size 就会爆炸，这时候再继续对这个块操作，复杂度也会随之爆炸。所以考虑在每进行完一次插入操作的时候，如果这个块的 size 超过了 2\times len（len 为当前钦定的块长）就进行 \text{rebuild}，重新构建分块。

每次 \text{rebuild} 的时间复杂度是 O(n)，此操作最多进行 O(\sqrt n) 次，所以这部分整体的时间复杂度是 O(n\sqrt n)。

Code

T7

区间乘，区间加，单点查询。

对每个块维护两个 tag，分别为 tag_{mul} 和 tag_{add}，记录乘和加的值。

对于整块的操作，如果是加就直接往 tag_{add} 里面加就行，如果是乘的话不仅要往 tag_{mul} 里面乘，还要把 tag_{add} 也乘一下，理由是乘法分配律，自己想一下就好。

对于非整块的操作，就先把所在块的 tag 给 pushdown 了，再暴力操作。

注意取模。

Code

T8

区间询问 x 的出现次数，随后立即把这个区间全部赋为 x。

啊这不一眼 Chtholly Tree 吗，哦原来已经被卡了啊，那没事了，伤心。

考虑整块的赋值操作直接维护每个块的 tag 即可。

查询的时候看每个块此时是否有 tag，有的话就看它是否为 x，如果是就直接加上，如果没有就暴力查。

这东西看起来很玄学，但是，虽然我们是 O(\sqrt n) 暴力查，但是查了之后就会立即给它赋上 tag 的，在之后的操作中，如果这个块被视作整块来操作，那么它就可以直接 O(1) 判断 tag，再往后也是这样。如果不是整块操作，那就是暴力查，但是每次查询最多有两个非整块，所以这个暴力操作被执行的次数是 O(n) 的，这东西整体复杂度就是 O(n\sqrt n)。

Code

T9

查询区间最小众数。

蒲公英。

处理 cnt 数组记录每个块中各个数字的出现次数，并按块处理它的前缀和 s。用 p 数组记录整块中的众数，即 p_{i,j} 表示第 i 个块到第 j 个块的众数。

预处理然后乱搞就行了，很暴力。

Code

题外话