毛子

四毛子 头好乱，不知道能干什么，心里好难受。 做题做不进去，颓废不能颓，所以学学新算法。 考虑如何解决静态区间差值为 \(1\) 最值问题。 首先分块，\(B = \lceil \frac{log_2 n}{2} \rceil\)。 整块怎么做，直接用 \(st\) 表，空间是 \(O(n)\) 的 ......

一种将相同小块合并处理，块间另行处理的算法。 ### $\pm 1 \text{ RMQ}$ 问题 > 有序列 $a,b$，其中 $a_i\in\{1,-1\}$，$b_i=\sum_{j=1}^i a_j$，静态查询序列 $b$ 最值。 > > 要求复杂度 $O(n)-O(1)$。 线段树可以做到 ......

## The Method of Four Russians 又名“四毛子算法”。概括来讲是一种分块后对小块的相同情况合并之后处理小块内，块间另行处理的算法。 一个典中点的例子是 $\pm1\ \text{RMQ}$，我们考虑块大小为 $B$，这样的话块间我们使用 $\text{ST}$ 表，块内一 ......