标准 RMQ 算法瞎写

upd:感觉之前写的有点问题，于是把所有准确数都加上了 O 符号

瞎写的，有什么问题赶紧来喷我

学习自 https://ljt12138.blog.uoj.ac/blog/4874 ，写的比我不知道高到哪里去了

就是一个严格 $O(n)-O(1)$ RMQ 的东西，不过 OI 中应该没什么用（（

期望 $O(n)-O(1)$ 那个就够了，常数又小又好写又没人卡你

算法流程大概是这样的

首先我们给序列整一个笛卡尔树，这样就把 RMQ 转化成了 LCA 问题

然后我们知道我们可以 RMQ 求 LCA

看到这里你可能觉得建树是意☆义☆不☆明的操作

不过我们看看 LCA 跑 RMQ 的性质，发现我们 RMQ 求 LCA 时是拉出了树的欧拉序

然后发现这东西相邻两个数的差距最多为 $1$

这东西叫做 ±1 RMQ

看到这里你可能觉得这还是意☆义☆不☆明的操作

不过我们发现差分之后，序列本质不同的区间减少了

想想我们期望 $O(n)-O(1)$ RMQ 的做法？那个救爷爷的套路？

不会也不要紧，反正你往下看也能看懂

我们序列分块，块长先整个 $B$

然后我们直接整块序列建 ST表，复杂度 $O(\frac{n}{B}\log n)$

然后我们刚才不是说了？本质不同区间减少了？

发现长度为 $B$ 的本质不同区间就 $O(2^B)$ 个

因此这部分枚举+存在表里面，就可以处理散块查询，配合整块查询可以做到 $O(1)$ 查询

取 $B=O(\log n)$ ，发现上面那一堆都是 $O(n)$

然后我们就得到了 $O(n)-O(1)$ 的 ±1 RMQ，得到了 $O(n)-O(1)$ 的 LCA，得到了 $O(n)-O(1)$ 的标准 RMQ 算法

---

upd：被指出有更好的实现方式，于是就学了学

感谢神仙 @youjiajun

注意： 这个东西似乎只能在 块长能压位的范围内有效 ，也就是说大概还有个 $O(\frac{\log n}{w})$ 的东西要乘上去，不过 OI 范围内应该可以忽略不计，本文也这么处理。

大概来说就是这样的

考虑我们还是按 $\log$ 对序列分块，然后之前的方式是通过建笛卡尔树转化成方便压缩的 ±1 RMQ

我们考虑能否直接压缩，仔细想想似乎也是可以的

我们这里以最大值为例

我们考虑对每一个块维护一个栈底到栈顶递减的单调栈，显然到某个数为止时栈内元素就是以当前结点为右端点时，区间最大值的所有可能答案

考虑此时栈内元素可能性只有 $O(2^{\log n})=O(n)$ 种，因此我们以每一个元素与左端点的距离进行状压，然后存在当前点上。

考虑我们只需要知道对于一个确定的右端点，某一个左端点在栈内的后继。

我们用类似压位 Trie 的方法，那么相当于求一个值域为 $O(\log n)$ 级别的后继，由于这里值域小，可以 $O(1)$ 做到

由此散块可以处理，在数据范围小时就是 $O(n)-O(1)$ 的

标准 RMQ 在 OI 中的应用至此已经彻底废掉了（（