今天在THUSC听了一天蛋疼课，为打发时间，YY了一些蛋疼RMQ算法……
首先给一个期望\(O(N)-O(1)\)的算法…… 把序列分成\(n^{0.5}\)段，预处理任意连续的段的RMQ,\(O(N)\). 预处理任意一个点到其最近的左/右关键点的RMQ, \(O(N)\)，然后一个查询如果包含了任意一个段，那么就可以直接利用预处理的结果\(O(1)\)回答，否则可以 发现落在同一段里的期望概率是\(1/n^{0.5}\)，而对这种询问直接暴力\(O(n^{0.5})\),期望还是\(O(1)\)的。
再给两个时间复杂度严格的算法……
第一个方法是将序列分成\(n/\log n\)段…… 然后段之间用ST维护\(O(N)\)，每一段内也ST维护(\(O(N/\log N)*O(\log N\log\log N)=O(N\log\log N)\))，这样任意一个询问都可以利用这个结果\(O(1)\)回答。于是时间复杂度\(O(N\log\log N)-O(1)\).
第二个方法也是将序列分成\(n/\log n\)段…… 段之间也是ST维护…… 但每一段内用线段树维护，这样查询是\(O(\log\log N)\)的（因为线段树只有有\(\log N\)个结点），于是时间复杂度\(O(N)-O(\log\log N)\).
还有一种瞎狗眼做法，就是考虑后面的那种方法…… 然后我们发现每一个\(O(\log N)\)长度的小段就是原问题的一个子问题，所以可以递归处理…… 每次规模是前一次的\(\log N\)，所以递归深度是\(O(\log^*N)\)的。所以最坏时间复杂度\(O(N\log^*N)-O(\log^*N)\).