RMQ

这里会记一些不那么基础的 RMQ 算法，同时也会向外拓展到增量法规建笛卡尔树之类的东西。

首先是基础的 RMQ，静态可以用 ST 表做到 \(O(n\log n)-O(1)\)，动态可以用线段树做到 \(O(n)-O(\log n)\)，当然还有一些奇技淫巧可以用 ST 表维护特殊的动态 RMQ。

现在来看不基础的。

询问区间定长

所有询问的区间长度均为 \(l\)。

单调队列不断右移可以做到 \(O(n)-O(1)\)，离线会更方便一点。

朴素随机区间询问

考虑分块，块长 \(b\)，共 \(\lceil \frac{n}{b}\rceil\) 块。

\(O(n)\) 维护出每块的最大值，用 ST 表对块做 RMQ，于是对于询问时的整块可以 \(O(1)\) 得到答案。

对于散块，可以线性维护每块前缀后缀最大值，同样做到 \(O(1)\) 询问。

总体时间复杂度 \(O(n+\frac{n}{b}\log\frac{n}{b})-O(1)\)，但是注意到询问可能在同一个块内，此时只能 \(O(b)\) 回答询问

但由于是随机区间，在同一个块内的期望复杂度为 \(O(\frac{b^2}{n})\)，所以询问是 \(O(q+q\frac{b^2}{n})\)。

非朴素区间询问