卧槽，$O(n)-O(1)$。
by fangzichang @ 2023-10-23 08:25:54
补充一下， 空间还很小 ( 至少应该是比 $st$ 表小的 )。 有很多地方可以优化都没加， 裸的代码。
by LG_kemeng @ 2023-10-23 08:26:58
遗憾的，注意到 $l,r$ 可以在同一块内。
by fangzichang @ 2023-10-23 08:27:41
查询在同块你查询不还是 $O(\sqrt n)$ 的。
by Nopain @ 2023-10-23 08:27:56
@[LG_kemeng](/user/246927) 每次询问左右端点在同一块，这样可以卡到 $O(n \sqrt{n})$
by zzxLLL @ 2023-10-23 08:28:40
@[LG_kemeng](/user/246927) 你考虑啥了，同块内查询你咋转成前后缀最值啊？
by Nopain @ 2023-10-23 08:29:44
@[LG_kemeng](/user/246927) 看代码你是暴力啊
by C6H6 @ 2023-10-23 08:30:14
@[zzxLLL](/user/469066) 是这样的。但卡块长和块起始位置可以莽过去，毕竟他也不是跟着你代码量身定做的。doge
by LG_kemeng @ 2023-10-23 08:30:22
你要是真能同块查询转前后缀最值查询，你咋不直接把这个算法用在整个序列？
by Nopain @ 2023-10-23 08:30:29
倒是可以搞个类 sqrt tree 的东西，那就是类猫树的 sqrt tree？
by fangzichang @ 2023-10-23 08:30:42