数列分块入门

分块是一种优秀的思想。

“数据”是分块的目的。不同于大多数树形数据结构，分块中访问数据是容易的，因此，它可以用比前者更简单的方式支持复杂的操作。

“标记”是分块最重要的过程。不同于大多数树形数据结构，分块大多数时候不需要支持标记与标记合并，因此，它能完成一些前者不能完成的事情。

本文接下来给出数论分块入门系列题目的题解。

如果以下题目存在作者知道的其他做法，会一并指出。

LOJ 6277 数列分块入门 1

区间加，单点查询

整块打加标记，散块暴力加，时间复杂度 \(O(q \sqrt n)\)。

另解：线段树 / 树状数组模板，时间复杂度 \(O(q \log n)\)。

LOJ 6278 数列分块入门 2

区间加，区间查询小于给定的数的数的个数

把每个块映射到新数组并从小到大排序，每次查询整块可以二分。

整块加不会改变元素相对大小，打加标记即可；散块暴力修改，并暴力重构。

时间复杂度 \(O(q \sqrt n \log n)\)。

LOJ 6279 数列分块入门 3

区间加，区间查询给定的数的严格前驱

同上一题，时间复杂度 \(O(q \sqrt n \log n)\)。

LOJ 6280 数列分块入门 4

区间加，区间和

整块打加标记，散块暴力加，时间复杂度 \(O(q \sqrt n)\)。

另解：线段树 / 树状数组模板，时间复杂度 \(O(q \log n)\)。

LOJ 6281 数列分块入门 5

区间开方（下取整），区间和

对于整块，如果块内最大值大于 \(1\) 则暴力开方，否则开方操作无效。

势能分析可以说明时间复杂度 \(O(q \sqrt n)\)。

另解：类似上述方法处理线段树的节点，时间复杂度 \(O(q \log n)\)。

LOJ 6282 数列分块入门 6

单点插入，单点询问

块状链表模板。

对原数列按 \(\sqrt {n + q}\) 为块长分块，块之间用链表结构连接，索引下标时至多跳 \(O(\sqrt {n + q})\) 块。

若插入操作后，块长超过 \(2 \sqrt {n + q}\)，则暴力将该块分裂为两个块。

时间复杂度 \(O(q \sqrt {n + q})\)。

LOJ 6283 数列分块入门 7

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

整块打加标记和乘标记，散块暴力加 / 乘。

这里的乘标记同时打在原数列和加标记上，即打乘标记时也要对加标记进行乘法。下放时，先下放乘标记，再下放加标记。

时间复杂度 \(O(q \sqrt n)\)。

另解：线段树模板，时间复杂度 \(O(q \log n)\)。

LOJ 6284 数列分块入门 8

区间查询数的出现次数，区间赋值

整块打赋值标记，散块暴力赋值，时间复杂度 \(O(q \sqrt n)\)。

另解：线段树，时间复杂度 \(O(q \log n)\)。

LOJ 6285 数列分块入门 9

区间众数

做法很多，可以用类似于 蒲公英 的分块；也可以离线用回滚莫队。时间复杂度 \(O(q \sqrt n)\)。