在线严格 O(n)-O(1) 静态区间绝对众数 (2)

Butterfly_qwq · 2025-11-27 12:58:16 · 算法·理论

前情提要：https://www.luogu.com.cn/article/5nb76ude。

本文需要感谢 masonxiong 对我的启发。

主播主播，分两次块还是太超模了，有没有只用分一次块的做法呢。

有的有的，我们考虑将猫树替换成 Sqrt Tree，只分一次块，复杂度就是 O(\frac{n}{B}\log\log n+B^{B+2})，随便取一取 B 就是线性的了。

至少 B\in[\log\log n,\frac{\log n}{\log\log n}] 内都是可行的。

感觉其实不如原做法，不是说的速度，速度我没测过不知道，我说的是，对长度为 6 的数组做一个 Sqrt Tree 很怪……

其实本质相同吧。