更优的 RMQ 问题解法

问题：给定长度为 $n$ 的序列 $a$ ，和 $m$ 次询问。每次询问 $[l,r]$ 内的最大值。

朴素解法

使用 ST 表可以做到 $O(n\log n)\sim O(1)$ 。

设 $f_{i,j}$ 表示 $\max\limits_{j\le k<j+2^i}\{a_k\}$ 。

那么就有 $f_{0,i}=a_i$ ， $f_{i,j}=\max\{f_{i-1,j},f_{i-1,j+2^{i-1}}\}$ 。

查询时设 $k=\lfloor\log n\rfloor$ 。

那么答案为 $\max\{f_{k,l},f_{k,r-2^k+1}\}$ 。

更优秀的解法

强壮的状压，羸弱的 Four Russian 。

首先做一个序列分块，每 $\log n$ 个数字为一块。

那么不难发现，如果预处理块内前后缀最值，以及整块的 ST 表，就可以做到 $O(n)\sim O(1)$ 。

但这肯定是错的，不然 Four Russian 太 naive 了。

容易发现当 $l,r$ 落到一个块中时不能这样做。

那么此时，我们可以考虑单调栈。

具体的，我们对每一个块维护一个单调递减的栈。

然后，设此时处理的块的左端点为 $i$ ，那么定义 $b_r$ 为单调栈中加入 $i\sim r$ 的所有数后留在栈中的数构成的集合的二进制数。

这样做肯定是对的，因为块的大小为 $\log n$ 。

那么，这样做之后，答案就是 $b_r$ 中 $l$ 对应的数之后第一个为 $1$ 的位置对应的数字。

具体看代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=6300;
int n,a[N],st[13][M],m,loc[N],pre[N],nxt[N],s[20],top,b[N],L[M],R[M],lg[M],pos[N];
void init(){
    for(int i=1;i<=n;i++)loc[i]=((i-1)>>4)+1;
    for(int i=1;i<=loc[n];i++)L[i]=((i-1)<<4)+1,R[i]=(i==loc[n]?n:(i<<4));
    for(int i=1;i<=n;i++)pos[i]=i-L[loc[i]];
    for(int i=1;i<=loc[n];i++){
        pre[L[i]]=a[L[i]];
        for(int j=L[i]+1;j<=R[i];j++)pre[j]=max(pre[j-1],a[j]);
        nxt[R[i]]=a[R[i]];
        for(int j=R[i]-1;j>=L[i];j--)nxt[j]=max(nxt[j+1],a[j]);
    }
    for(int i=1;i<=loc[n];i++)st[0][i]=pre[R[i]];
    for(int i=1;i<=12;i++)for(int j=1;j+(1<<i)-1<=loc[n];j++)
        st[i][j]=max(st[i-1][j],st[i-1][j+(1<<i-1)]);
    for(int i=1;i<=loc[n];i++){
        top=0;
        for(int j=L[i];j<=R[i];j++){
            b[j]=(j==L[i]?0:b[j-1]);
            while(top&&a[s[top]]<=a[j])b[j]^=(1<<pos[s[top]]),--top;
            s[++top]=j;
            b[j]^=(1<<pos[j]);
        }
    }
    for(int i=2;i<=loc[n];i++)lg[i]=lg[i>>1]+1;
}
int st_query(int l,int r){
    int k=lg[r-l+1];
    return max(st[k][l],st[k][r-(1<<k)+1]);
}
int query(int l,int r){
    if(loc[l]!=loc[r]){
        int res=max(nxt[l],pre[r]);
        if(loc[l]+1<=loc[r]-1)
            res=max(res,st_query(loc[l]+1,loc[r]-1));
        return res;
    }
    return a[l+__builtin_ctz(b[r]>>pos[l])];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    init();
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",query(l,r));
    }
    return 0;
}