出题人滚出来写题解了
题意简化
给定 NNN 个数和 QQQ 次询问，每次询问求出 [l,r][l,r][l,r] 中最大值的下标（从 111 开始）。
暴力
显然地，我们可以暴力循环枚举 [l,r][l,r][l,r] 中的每一个数，打擂台寻找最大值，并顺便记录下标。
时间复杂度：O(nq)O(nq)O(nq).
ST 表
可以发现，QQQ 次操作中没有修改操作，而且求的是最大值的下标，是一个静态区间 RMQ 问题。可以用 st 表解决。
ST 表简介
预处理
st 表是基于倍增思想实现的。暴力的方式很容易想到：用 fi,jf_{i,j}fi,j 表示从 iii 开始，jjj 个数之内的最大值。
如何求呢？可以使用 dp 的思想，把 jjj 分解成 222 部分，可以得到：fi,j=max(fi,j2,fi+j2,j+12)f_{i,j}=\max(f_{i,\frac{j}{2}},f_{i+\frac{j}{2},\frac{j+1}{2}})fi,j =max(fi,2j ,fi+2j ,2j+1 ).
然后我们思考如何把 jjj 循环简化到 logn\log nlogn。注意到每一个数都可以由若干个 2k (k≥0)2^k \space (k \geq 0)2k (k≥0) 之和得到（思考思考二进制）。
所以设 sti,jst_{i,j}sti,j 表示从 iii 开始，2j2^j2j 个数之内的最大值。
依旧使用 dp 思想，得：sti,j=max(sti,j−1,sti+2j−1,j−1)st_{i,j}=\max(st_{i,j-1},st_{i+2^{j-1},j-1})sti,j =max(sti,j−1 ,sti+2j−1,j−1 ) .
然后处理一下边界：sti,0=aist_{i,0}=a_isti,0 =ai .
注意到我们是按照 jjj 进行转移的，所以循环的时候先循环 jjj，后循环 iii.
这样就行了，时间复杂度为 O(nlogn)O(n \log n)O(nlogn).
处理询问
但是，这样只能处理区间 2m2^m2m 长度的询问了，如何一般化呢？
首先，把区间 [l,r][l,r][l,r] 分解为 [l,k][l,k][l,k] 和 [r−k+1,k][r-k+1,k][r−k+1,k]。此时，我们惊奇的发现：kkk 只需要取 2m2^m2m，并且让这两个区间完全覆盖 [l,r][l,r][l,r] 就好了！
贪心地想，我们如果 kkk 取到最大，一定是可以的。所以我们取 k=2⌊log2(r−l+1)⌋k=2^{\lfloor \log_2(r-l+1) \rfloor}k=2⌊log2 (r−l+1)⌋ 即可。
然后我们取这两个区间的 st 的最大值就好了。
恭喜你，学会了 st 表！
存储下标
但是，这道题需要输出下标。所以不能用原本的 st 表，需要小小修改一下。
我们可以把 st 改成存储下标，抛弃 max\maxmax 求最大值，而是手动判断 sti,j−1,sti+2j−1,j−1st_{i,j-1},st_{i+2^{j-1},j-1}sti,j−1 ,sti+2j−1,j−1 谁的值更大。
处理询问的时候，也是这样，把这两个分解出来的区间手动判断谁更大。
时间复杂度：O(nlogn+q)O(n \log n + q)O(nlogn+q).
线段树
除了 st 表，似乎还有一种求解 RMQ 问题的数据结构。要不是我打了标签绝对不写线段树
线段树想必很熟悉了，不再介绍。
需要修改的部分只有 push_up 和 query.
相较于 st 表，线段树在空间复杂度大大优化。
时间复杂度：O(n+qlogn)O(n+q \log n)O(n+qlogn).
