出题人滚出来写题解了

题意简化

给定 $N$ 个数和 $Q$ 次询问，每次询问求出 $[l,r]$ 中最大值的下标（从 $1$​ 开始）。

暴力

显然地，我们可以暴力循环枚举 $[l,r]$​ 中的每一个数，打擂台寻找最大值，并顺便记录下标。

时间复杂度：$O(nq)$.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+35;
int n,q,l,r,res,ans;
int a[MAXN];
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(q--){
        cin>>l>>r;
        res=ans=0;
        for(int i=l;i<=r;i++){
            if(a[i]>res){
                res=a[i];
                ans=i;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

st 表

可以发现，$Q$ 次操作中没有修改操作，而且求的是最大值的下标，是一个静态区间 RMQ 问题。可以用 st 表解决。

st 表简介

预处理

st 表是基于倍增思想实现的。暴力的方式很容易想到：用 $f_{i,j}$ 表示从 $i$ 开始，$j$ 个数之内的最大值。

如何求呢？可以使用 dp 的思想，把 $j$ 分解成 $2$ 部分，可以得到：$f_{i,j}=\max(f_{i,\frac{j}{2}},f_{i+\frac{j}{2},\frac{j+1}{2}})$.

然后我们思考如何把 $j$ 循环简化到 $\log n$。注意到每一个数都可以由若干个 $2^k \space (k \geq 0)$ 之和得到（思考思考二进制）。

所以设 $st_{i,j}$ 表示从 $i$ 开始，$2^j$ 个数之内的最大值。

依旧使用 dp 思想，得：$st_{i,j}=\max(st_{i,j-1},st_{i+2^{j-1},j-1})$​.

然后处理一下边界：$st_{i,0}=a_i$.

注意到我们是按照 $j$ 进行转移的，所以循环的时候先循环 $j$，后循环 $i$.

这样就行了，时间复杂度为 $O(n \log n)$.

处理询问

但是，这样只能处理区间 $2^m$ 长度的询问了，如何一般化呢？

首先，把区间 $[l,r]$ 分解为 $[l,k]$ 和 $[r-k+1,k]$。此时，我们惊奇的发现：$k$ 只需要取 $2^m$，并且让这两个区间完全覆盖 $[l,r]$ 就好了！

贪心地想，我们如果 $k$ 取到最大，一定是可以的。所以我们取 $k=2^{\lfloor \log_2(r-l+1) \rfloor}$​ 即可。

然后我们取这两个区间的 st 的最大值就好了。

恭喜你，学会了 st 表！

存储下标

但是，这道题需要输出下标。所以不能用原本的 st 表，需要小小修改一下。

我们可以把 st 改成存储下标，抛弃 $\max$ 求最大值，而是手动判断 $st_{i,j-1},st_{i+2^{j-1},j-1}$ 谁的值更大。

处理询问的时候，也是这样，把这两个分解出来的区间手动判断谁更大。

时间复杂度：$O(n \log n + q)$.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+35;
int n,q,l,r,len;
int a[MAXN],logs[MAXN],st[MAXN][20];
inline void read(int &x){//快读
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return;
}
int main(){
    read(n);
    read(q);
    for(int i=1;i<=n;i++){
        read(a[i]);
        st[i][0]=i;//边界状态
        if(i^1) logs[i]=logs[i>>1]+1;//预处理 log
    }
    for(int j=1;1<<j<=n;j++){//预处理 st 表
        for(int i=1;i<=n;i++){
            if(i+(1<<j)-1>n) break;
            if(a[st[i][j-1]]>=a[st[i+(1<<j-1)][j-1]]) st[i][j]=st[i][j-1];//存储下标
            else st[i][j]=st[i+(1<<j-1)][j-1];
        }
    }
    while(q--){
        read(l);
        read(r);
        len=logs[r-l+1];
        if(a[st[l][len]]>=a[st[r-(1<<len)+1][len]]) printf("%d\n",st[l][len]);//处理询问
        else printf("%d\n",st[r-(1<<len)+1][len]);
    }
    return 0;
}

线段树

除了 st 表，似乎还有一种求解 RMQ 问题的数据结构。要不是我打了标签绝对不写线段树

线段树想必很熟悉了，不再介绍。

需要修改的部分只有 push_up 和 query.

相较于 st 表，线段树在空间复杂度大大优化。

时间复杂度：$O(n+q \log n)$.

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+35;
struct node{
    int l,r,maxx;
};
int n,q,l,r;
int a[MAXN];
node sgt[MAXN<<2];
inline void read(int &x){//快读
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return;
}
inline int ls(const int &p){return p<<1;}//线段树
inline int rs(const int &p){return p<<1|1;}
inline void push_up(const int &p){
    if(a[sgt[ls(p)].maxx]>=a[sgt[rs(p)].maxx]) sgt[p].maxx=sgt[ls(p)].maxx;
    else sgt[p].maxx=sgt[rs(p)].maxx;
    return;
}
inline void build(const int &l,const int &r,const int &p){
    sgt[p]={l,r,0};
    if(l>=r){
        sgt[p].maxx=l;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    push_up(p);
    return;
}
inline int query(const int &l,const int &r,const int &ql,const int &qr,const int &p){
    if(l>=ql&&r<=qr) return sgt[p].maxx;
    int res=0,mid=l+r>>1;
    if(mid>=ql) res=query(l,mid,ql,qr,ls(p));
    if(mid<qr){
        if(res==0) res=query(mid+1,r,ql,qr,rs(p));
        else if(a[res]<a[query(mid+1,r,ql,qr,rs(p))]) res=query(mid+1,r,ql,qr,rs(p));
    }
    return res;
}
int main(){
    read(n);
    read(q);
    for(int i=1;i<=n;i++) read(a[i]);
    build(1,n,1);//建树
    while(q--){
        read(l);
        read(r);
        printf("%d\n",query(1,n,l,r,1));//处理询问
    }
    return 0;
}