普通分块

原理

非常简单且暴力，以区间加，区间和为例。

考虑把序列分成 \(\lceil\sqrt{n}\rceil\) 块，其中第 \(i,(1 \le i \le \lfloor\sqrt{n}\rfloor)\) 段的边界是 $l=(i-1)\times \lfloor\sqrt{n}\rfloor +1,r=i \times \lfloor\sqrt{n}\rfloor $ 。

对于第 \(\lceil\sqrt{n}\rceil\) 块，如果说第 \(\lfloor\sqrt{n}\rfloor\) 块的右边界没有达到 \(n\) ，那么就让第 \(\lceil\sqrt{n}\rceil\) 块维护区间 \([i\times \lfloor \sqrt{n} \rfloor +1,n]\) 即可。

反之是不会有第 \(\lceil\sqrt{n}\rceil\) 块的，因为此时 \(\lfloor\sqrt{n}\rfloor=\lceil\sqrt{n}\rceil=\sqrt{n}\)。

然后预处理出每一个位置 \(i\) 在分块之后属于哪一个块 （\(\text{belong}_i\)）。

对于每一个块，记录其左右边界以及块内和，并维护一个类似于懒标记的 \(\text{add}\)，表示这个块里的所有数都被加过多少。

每次操作区间 \([l,r]\) 的时候分情况讨论：

1. 如果 \(\text{belong}_l=\text{belong}_r\) ，那么直接暴力修改区间 \([l,r]\)。
2. 反之，把这个区间两边非整块的部分暴力修改，然后为所有整块的部分打上标记。

查询的时候也比较类似：

1. 直接暴力扫一遍 \([l,r]\) ，求和即可（不要忘记把标记加上）
2. 非整块部分暴力扫，整块部分用块内和加上 \(\text{add}\) 标记。

因为最多只有 \(\lceil\sqrt{n}\rceil\) 块，所以复杂度是 \(\text{O}((n+q)\times \sqrt{n})\)。

习题

LOJ6277. 数列分块入门 1

区间加单点查，只需要分块的时候记录 \(\text{add}\) 配以暴力修改。

查询时带上标记即可。

Code

Luogu3372 【模板】线段树 1

区间加区间和，分块之后按照上面“原理”部分的做法来就行。

只需要注意一下什么时候要更新块内和，什么时候要打标记就行。

Code

LOJ6278. 数列分块入门 2

区间加，区间查询比 \(c^2\) 小的数的个数。

首先继续分块，仍旧维护每一个块的 \(\text{add}\) 标记。

考虑如何查询区间有多少个数比 \(c^2\) 小。

沿用“小段朴素，大段维护”的思想，我们在查询时在两边的两个不完整块进行暴力扫描。

然后对于每一个被包含的整块，考虑在块内二分。

为了二分，我们需要额外多对于每一个块维护一个有序的序列 \(v\) 。

当我们暴力修改小段的时候，这个小段所属的块的单调性就会改变，所以我们需要对这个块的 \(v\) 进行重排。

如果是大段打标记的话，因为块内每一个数都被加了同一个数，所以单调性不会改变，不需要重排。

那么大段查询的时候只需要把 \(c^2\) 减去每个块的标记之后然后二分就可以了。

初始化的时候不要忘记把元素扔进 \(v\) 里面！

Code

LOJ6279. 数列分块入门 3

区间加，区间询问前驱。

沿用上一个题的思想，我们小段暴力，大段二分。

但是如果直接对块内二分的话可能会因为没去重而爆炸。

所以我们考虑把上面那题的 std::vector 换成 std::set 。

那么只需要在每个块的 std::set 里面用 lower_bound 二分之后令迭代器减一，就可以了。

（因为 lower_bound 求的是大于等于 \(x\) 的最小元素的迭代器，迭代器在 std::set 里面减一之后就是前驱了）

当然，二分的时候一定要使用容器本身的lower_bound ，不然效率会及其低下（具体可以看这里）。

另外不要忘记初始化的时候把元素扔进 std::set 里面，也不要忘记判二分之后二分出 s.begin() 的情况。

Code