来自 hzwer 的九道非常经典的分块题。

目前可以在 LOJ 上提交：Here

---

1.

给出一个长度为 \(n\) 的数列，支持区间加，单点查值。

将序列分成长度为 \(S\) 的 \(\lceil\frac{n}{S}\rceil\) 块。

设我们的操作区间为 \([l,r]\)，称被其完全包含的块为整块，否则为散块。

可以发现整块的数量不超过 \(\lceil\frac{n}{S}\rceil\)，散块的数量不超过 \(2\)，于是散块中元素的个数不超过 \(2S\)。

加法操作就可以在这 \(\lceil\frac{n}{S}\rceil\) 个整块上打标记，散块中的元素暴力加。

一次操作的时间复杂度为 \(O(\lceil\frac{n}{S}\rceil+S)\)。

单点查询就直接输出该位置的值加上所在块的标记，复杂度是 \(O(1)\) 的。

注意到我们需要平衡修改操作的复杂度，即让 \(\lceil\frac{n}{S}\rceil\) 和 \(S\) 尽量差的小。

于是取 \(S=\sqrt n\) 就可以做到 \(O(\sqrt n)\)。

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

---

2.

给出一个长度为 \(n\) 的数列，支持区间加，求一个区间中小于一个数 \(x\) 的元素数量。

可以考虑在每个块内维护原序列排序后的序列。也就是每个块维护一个原块，和一个排序后的块。

那么对于一个块的询问就可以 \(O(\log S)\) 二分一下完成。

散块暴力统计，时间复杂度 \(O(S)\)。

那么一次询问的复杂度为 \(O(\lceil\frac{n}{S}\rceil\log S+S)\)。

对于修改操作，可以发现对于一个整块进行整体加法并不会改变其有序性。所以可以直接在 \(\lceil\frac{n}{S}\rceil\) 个整块上打加法标记，复杂度 \(O(\lceil\frac{n}{S}\rceil)\)。

散块暴力做加法，同时重新排序，时间复杂度 \(O(S+S\log S)\)。

于是一次修改的复杂度为 \(O(\lceil\frac{n}{S}\rceil+S\log S)\)。

取 \(S=\sqrt n\) 可以做到 \(O(\sqrt n\log n)\)。