一种将相同小块合并处理，块间另行处理的算法。
\(\pm 1 \text{ RMQ}\) 问题
有序列 \(a,b\)，其中 \(a_i\in\{1,-1\}\)，\(b_i=\sum_{j=1}^i a_j\)，静态查询序列 \(b\) 最值。
要求复杂度 \(O(n)-O(1)\)。
线段树可以做到：\(O(n)-O(\log n)\)，ST 表可以做到 \(O(n\log n)-O(1)\)，都不牛。
考虑四毛子。设块长为 \(B\)。
一共有 \(2^B\) 种不同小块，考虑对于每种小块暴力求出块内任意区间的最值，这部分时间复杂度为 \(O(2^BB^2)\)。
对于整块，我们用 ST 表维护下任意区间整块的最值，这部分时间复杂度为 \(O(\frac{n}{B}\log \frac{n}{B})\)。
如此询问时即可做到 \(O(1)\) 查询。
取 \(B=\frac{\log n}{2}\)，复杂度为 \(O(n+\sqrt n\log n+\frac{2n}{\log n}\log \frac{2n}{\log n})\)，由于 \(\frac{2n}{\log n}<n\)，所以右侧复杂度小于 \(O(n)\)，总复杂度为 \(O(n)\)。
\(\text{RMQ}\) 问题
现在升级成真正的 \(\text{RMQ}\) 问题，想想能不能转化为前一个问题。
是可以的。
考虑建出序列的笛卡尔树，作用类似离散化，除此之外还将序列转化为了非常好的树形结构。
此时询问 \(\text{RMQ}\) 被我们转化为了询问树上两节点的 \(\text{lca}\)。\(\text{lca}\) 和 \(\text{RMQ}\) 有什么其它关联呢？在某个范围内，\(\text{lca}\) 的深度是最小的。
考虑把树再次变成序列，将笛卡尔树转成欧拉序。此时我们发现在深度维度上相邻两项的差值再次变成了 \(\pm 1\)（钦定叶子节点只放入一次）。
设某节点 \(i\) 第一次进入欧拉序的位置为 \(dfn_i\)，第二次进入欧拉序的位置为 \(low_i\)，则查询时我们直接找到两个节点对应的四个值取最小最大作为区间端点查询即可。唯一不同的一点是我们还需要额外记录最值在序列中的对应位置，从而找到其对应的原值，不过这个就是小问题了。
于是我们便可以做这道题了。哦，但是这道题很卡空间，还需要利用下数据的随机性。
某应用题目
给定二维数组 \(A_{n,n}\)，\(A_{i,j}\) 表示元素 \(j\) 是否在集合 \(i\) 中。
请输出 \(C_{n,n}\)，其中 \(C_{i,j}\) 表示集合 \(i\) 是否包含于 \(j\)。
其中 \(n\le 5000\)。
考虑将元素分块，每 \(B\) 个元素一个块。则一共有 \(2^B\) 种不同的小块。
不妨对每种小块，处理出若其为第 \(i\) 个小块，在对应位置可以成为其超集的原题集合的集合 \(S\)。如果我们能求出这个，我们就可以对于每个原题集合，将其每个块的超集集合取交，即可得答案。这部分时间复杂度为 \(O(\frac{n^3}{B\omega})\)。
那么问题就来到了如何求出每种小块在第 \(i\) 个位置上时，在对应位置可以成为其超集的原题集合的集合。发现其实可以和上一部分一个思路：不妨预处理出块内第 \(x\) 个位置为 \(1\) 的原题集合的集合，则对于二进制表示为 \(p\) 的一个块，其超集集合即为所有值为 \(1\) 位置的集合之并。而前者可以通过找 lowbit 递推转移，则这部分时间复杂度为 \(O(2^B\frac{n^2}{B\omega}+n^2)\)。
取个 \(B=O(\log n)\) 大概就是最优的了，实际取到 \(B=8\) 差不多。
Ending
当分块区间状态数很少（一般每个位置只有两个取值）时，就可以考虑能否将小块合并处理。
四毛子一般会优化掉一个 log，也可以通过复杂度层面想到这东西。
不过 1 log 而已，所以它主要还是起到锦上添花而非雪中送炭的效果。