今天我突发奇想，发现四毛子算法是可以上猫树的，然后我就去实现了一个。

但是我测出来和猫树跑的一样快（我偷懒没写块内求前后缀，所以我删掉了所有的查询，毕竟优化的主要是预处理复杂度）。

猫树版四毛子

https://www.luogu.com.cn/record/132483838

我分析了一下，我开了两颗猫树，第一颗大小为 $O(\frac{n}{B})$，预处理复杂度 $O(\frac{n}{B}\log\frac{n}{B})$，第二颗大小为 $n$，但是只在区间长度小于 $B$ 的时候再去做前后缀处理，那么我总共会做 $\log B$ 层这样的东西，复杂度 $O(n\log B)$，取 $B = \log n$，复杂度应该是一样的啊。

可能是因为我乱斗 stl 导致常数爆炸，但应该也不至于 0 优化吧。

不懂。有没有老哥帮我康康。