RMQ 合集

First Post:

Last Update:

Word Count:
2.2k

Read Time:
10 min

Page View: loading...

upd 2021/9/20： 更新。

暴力想必算了。

倍增

或 Sparse Table。

考虑 表示 ，显然可以 。

但是因为 RMQ 问题满足可重复贡献（即 ），所以我们并不需要把 个区间完美的拼起来，只需要找到两个足够长的区间使它们拼起来能覆盖整个需要的区间即可，所以 。

1
2
3
4
5
6
7
for(int j=1;j<=log2[n];++j)
    for(int i=1;i+(1<<j)-1<=n;++i)
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
for(int i=1;i<=m;++i){
    int x=read(),y=read(),s=log2[y-x+1];
    printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
}

线段树等数据结构

代码想必算了。

猫树

线段树的变种。

对每个树上结点维护前后缀，用 zkw 的方式补全线段树，然后快速算 LCA 什么的。

代码会了但是没必要放这里。

Four Russians

首先把整个序列分成 块，然后做 ST 表。

这样可以把询问分成中间一堆整块，这个可以 ，与两边的散块（或者一个散块）。

对于散块怎么办呢？

再跑一个 ST 表。

没写过。

约束 RMQ

敲黑板：这个是 的。

首先要跑这个东西需要满足一个条件：相邻两数差的绝对值必须为 1（我们一会会去掉这个条件）。

首先考虑 Four Russians 算法，我们发现如果询问有两个散块的话，再对散块使用 ST 表就很蠢了。

我们直接处理一个前缀和后缀就可以加速到 .

然后考虑两端点在同一块里面的情况。

你思考因为相邻两数差的绝对值为 1，所以差分之后就变成一堆 1 与 -1 。这些形成的序列形成的不同的序列显然只有 种，然后有一个很棒的性质，差分后相同的序列，对于一个区间询问，最值的位置一定是固定的。

似乎没什么用，但我们可以把块弄的更小些：，然后就会有 。

暴力预处理所以本质不同的块，得到每个区间询问的答案，可以做到 。

实际上可以进一步调整块长来均摊（当然你要是闲得慌也可以写 ST 处理），不过没什么用。

然后我们思考怎么把一般 RMQ 转化为约束 RMQ。

首先，我们把序列变成一颗笛卡尔树，这样 RMQ 就变成了 LCA，然后对这颗树跑一个欧拉序，那么显然就有相邻两个数差的绝对值为 1。

代码没有因为不实用。

2021/9/20 更新： emm，我星期三学完的约束 RMQ 星期日就直接出现在了初赛考题里。狂暴押题组长

基于状态压缩的伪线性 RMQ

我们发现 Four Russians 的瓶颈在于对块内求 RMQ。

我们考虑单调栈。

啊单调栈有什么性质呢？

越靠前的越大，而且单调栈中的顺序肯定是原先的顺序。

那么如果我们要在单调栈上维护一个后缀，就直接找到在单调栈中第一个在位置上超过某个数的就行。

例如 3 6 2 5 4 1 的单调栈为 6 5 4 1 然后我们要找到 3 的后缀最大值就是 6 ，2 的后缀最大值就是 5。

意会意会真的简单

但是这样只维护了一个后缀，那么右端点的问题就……直接对每个后缀维护一个单调栈。

然后你成功的得到了一个 的东西。

不过，你发现如果我们把这个东西套到 Four Russians 里面还是可以搞出一个 的东西的。

但是还是非常非常费拉

然后我们注意到 ，所以我们考虑把单调栈变为一个表示某个数是否在栈内的零一序列，然后用个整数压起来，这样就可以避免预处理的时候要复制整个栈带来的时间复杂度。

然后我们祭出一个在今年终于可以使用的东西：builtin。

我们主要使用 __builtin_ctz （二进制后缀 0 的个数）与 __builtin_clz （二进制前导 0 的个数）（只用一个也行）。

显然 那么就是

代码（根据 OI-Wiki 改的，没什么区别）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cmath>
#include<cstdio>
#include<algorithm>
#define uni unsigned
#define reg register
using namespace std;
const int N=1e5+5,M=20,FSIZE=1<<26;
int m,st[21];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF;
int read(){
    uni x=0;
    for(;47>*InF||*InF>58;++InF);
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    return(x);
}
void write(reg uni x){
    if(!x) *OnF++=48;
    for(;x;x/=10) st[++st[0]]=x%10;
    for(;st[0];*OnF++=st[st[0]--]^48);
    *OnF++='\n';
}
struct RMQ{
    int n,A[N],BS,S[N][M],Pow[M],Log[N],in[N],Pos[N],Pre[N],Sub[N],F[N];
    void buildST(){
        int cur=0,id=1;
        Pos[0]=-1;
        for(int i=1;i<=n;++i) {
            S[in[i]=id][0]=max(S[id][0],A[i]);
            Pos[i]=in[i-1]==in[i]?Pos[i-1]+1:0;
            if(++cur==BS){
                cur=0;
                ++id;
            }
        }
        id-=!(n%BS);
        for(int i=Pow[0]=1;i<M;++i) Pow[i]=Pow[i-1]<<1;
        for(int i=2;i<=id;++i) Log[i]=Log[i>>1]+1;
        for(int i=1;i<=Log[id];++i)
            for(int j=1;j+Pow[i]-1<=id;++j)
                S[j][i]=max(S[j][i-1],S[j+Pow[i-1]][i-1]);
    }
    void buildSubPre(){
        for(int i=1;i<=n;++i)
            Pre[i]=in[i]==in[i-1]?max(Pre[i-1],A[i]):A[i];
        for(int i=n;i;--i)
            Sub[i]=in[i]==in[i+1]?max(Sub[i+1],A[i]):A[i];
    }
    void buildBlock(){
        static int S[N],top;
        for(int i=1;i<=n;++i){
            if(in[i]!=in[i-1]) top=0;
            else F[i]=F[i-1];
            while(top&&A[S[top]]<=A[i]) F[i]^=1<<Pos[S[top--]];
            F[S[++top]=i]|=1<<Pos[i];
        }
    }
    void init(){
        for(int i=1;i<=n;++i) A[i]=read();
        BS=log2(n)*1.5;
        buildST();
        buildSubPre();
        buildBlock();
    }
    int queryMax(int l, int r) {
        int bl=in[l],br=in[r];
        if(bl!=br){
            int ans1=0;
            if(br-bl>1){
                int p=Log[br-bl-1];
                ans1=max(S[bl+1][p],S[br-Pow[p]][p]);
            }
            return(max(ans1,max(Sub[l],Pre[r])));
        }else return(A[l+__builtin_ctz(F[r]>>Pos[l])]);
    }
}R;
int main(){
    fread(BuF,1,FSIZE,stdin);
    R.n=read();m=read();
    R.init();
    for(int i=0,l,r;i<m;++i){
        l=read();r=read();
        write(R.queryMax(l,r));
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}

二次分块实现方式

自己随意口胡的。

这个二次分块实现主要是查询的时候常数更小，大约 1000000 的 会比 ST 表实现快 ，预处理慢一些。

没什么好说的，把 ST 表换成根号分块套根号分块，然后对每一层分块暴力求块间答案。

时间复杂度 ，这里需要注意的是当 的时候就必须使用 long long 了，损失的性能基本可以忽略不计，然后可以支持 ，不是很大，但能用就行。

然后就是 __builtin_ 函数的 long long 版本就直接在后面加 ll 就行，例如 __builtin_ctzll 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define uni unsigned
#define reg register
using namespace std;
const int N=1000010,T0=1010,T1=34,FSIZE=1<<26;
int n,m,st[21];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF;
int read(){
    uni x=0;
    for(;47>*InF||*InF>58;++InF);
    for(;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    return(x);
}
void write(reg uni x){
    if(!x) *OnF++=48;
    for(;x;x/=10) st[++st[0]]=x%10;
    for(;st[0];*OnF++=st[st[0]--]^48);
    *OnF++='\n';
}
struct rmq{
    int a[N],b0[T0][T0],b1[T0][T1][T1],in0[N],in1[N],p0[N],n0[N],p1[N],n1[N],pos[N],ms,B0,B1;
    uni st[N],we[N];
    rmq(reg int n){
        B1=sqrt(B0=sqrt(n));
        for(reg int i=0,x,y,z;i<n;++i){
            y=in1[i]=(z=i-(x=in0[i]=i/B0)*B0)/B1;
            pos[i]=z%B1;
            b0[x][x]=max(b0[x][x],a[i]=read());
            b1[x][y][y]=max(b1[x][y][y],a[i]);
        }
        ms=in1[B0-1];
#define rep(s,p,r) for(reg int k=p+1;k<=r;++k) s[p][k]=max(s[p][k-1],s[k][k]);
        for(reg int i=0;i<in0[n-1];++i) rep(b0,i,in0[n-1]);
        for(reg int i=0;i<=in0[n-1];++i)
            for(reg int j=0;j<=ms;++j) rep(b1[i],j,ms);
#define get(t,s,x,y) t[x]=a[i];if(s[x]==s[y]) t[x]=max(t[x],t[y]);
        p0[0]=p1[0]=a[0];
        for(reg int h=0,i=st[0]=1;i<n;++i){
            get(p0,in0,i,i-1);
            get(p1,in1,i,i-1);
            if(in1[i]==in1[i-1]) st[i]=st[i-1];
            else h=i;
            for(reg uni &x=st[i],tp;x&&a[h+(tp=31-__builtin_clz(x))]<a[i];x^=1u<<tp);
            st[i]|=we[i]=1u<<pos[i];
        }
        for(reg int i=n-1;~i;--i){
            get(n0,in0,i,i+1);
            get(n1,in1,i,i+1);
        }
    }
    int query(int x,int y){
        return(in0[x]!=in0[y]?max(b0[in0[x]+1][in0[y]-1],max(n0[x],p0[y])):
            in1[x]!=in1[y]?max(b1[in0[x]][in1[x]+1][in1[y]-1],max(n1[x],p1[y])):
            a[x+__builtin_ctz(st[y]>>pos[x])]);
    }
};
int main(){
    fread(BuF,1,FSIZE,stdin);
    n=read();m=read();
    for(static rmq a(n);m;--m){
        int x=read()-1,y=read()-1;
        write(a.query(x,y)); 
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}
≡