这边提供一个 $O(n)$ 的分块做法st表模板题肯定不用st表过啊。

经典分块块大小 $sqrt(n)$ ，对每一块求出最大值， 预处理 $O(n)$ ， 每次询问 $\sqrt{n}$ ，显然挂掉。 考虑预处理出第 $i$ 块到第 $j$ 块的最大值， 复杂度 $\sqrt{n} \times \sqrt{n} = O(n)$， 这样对于整块询问可以做到 $O(1)$， 但是零散块的暴力容易被卡。 考虑对每一块多维护一个前缀最大值和后缀最大值，就可以做到询问 $O(1)$ 了。

代码贴在底下， 无吸氧 $761ms$ ，$rank$ 榜 $17/527$ ，跑的飞快。整活做法， 仅供参考。