感觉第二个用处不会很大，毕竟期望只有1个询问落到同一块里面（
by _5011_ @ 2021-03-17 21:21:50
第一个并没有看懂是怎么做到低于 $O(n)$ 预处理的。。。你不是至少要弄出 $O(n)$ 个数组的值吗。。。
by _5011_ @ 2021-03-17 21:25:34
\*$O(n)$ 个值
by _5011_ @ 2021-03-17 21:26:48
@[w33z8kqrqk8zzzх33](/user/91127) 是 $\frac{m}{\sqrt{n}}$ 罢。
by JS_TZ_ZHR @ 2021-03-17 21:37:23
我以前好像分析过第二个优化，效果是可以优化掉 $\dfrac 1 3$ 的暴力计算
by critnos @ 2021-03-17 21:51:00
等下子，好像不是
by critnos @ 2021-03-18 13:20:51
@[mcyl35](/user/203623) 效果是优化掉块间最值不在区间内的情况，但不知道是多少
by JRzyh @ 2021-03-21 09:39:50
@[Zhaoyuhang2008](/user/242524) 不是块间最值在区间内的情况吗
by critnos @ 2021-03-21 13:29:45
等下，是说整块的最值在 $[l,r]$ 内吗
by critnos @ 2021-03-21 13:31:04
@[mcyl35](/user/203623) 刚才naive了
区间内最值 $<pre_{l-1} $ 且 $<las_{r+1} $
by JRzyh @ 2021-03-21 13:39:57