题解：P3865 【模板】ST 表 && RMQ 问题

· · 题解

算法说明

这是一个非常经典的 ST 表问题。我们可以看到限制时间可知，这个模版题对我们的查询复杂度需要控制在 O(1)，所以我们可以分如下几步。ST 表一般分为建表和查询两步。

第一步-建表

第一步，建表，写 ST 表首先是要建表，根据题可知，他要求我们求的是区间最大值，那么我们需要建的是最大值的 ST 表。具体实现代码如下，时间复杂度是 O(N \cdot \log N)，其实在这里有一点倍增法的思路在内了。

第一步正确性说明

而在这里，需要一点点的正确性的证明：如果该区间长度为 len，那么也存在 2^p=len，那么有 k=\lfloor p \rfloor，而此时显而易见 2^k \le len，那么 2^{k+1} \ge len。因此可以得出 k= \lfloor \log_2 len \rfloor。\ 那这很显然会有一定区间重合，但这并不影响答案。

建表步骤代码实现

void jb(){
    for(int i=1;i<=n;i++) F[i][0]=a[i];
    int k=log2(n);
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
        }
    }
}

第二步-查询

第二步，查询，我们可以通过一个公式去得出他的结果。我们可以知道他可以在 O(1) 的复杂度的查询时间，且我们可以通过 max(F[l][k],F[r-(1<<k)+1][k]); 进行一次求值。那么我们就需要考虑 k 的取值了。由于实在区间内所以必有左区间与右区间，假设左区间位置为 l，右区间为 r，则我们可以得出区间内个数有 r-l+1，那么我们可以立即得出代码。

证明

这里稍微证明了一下，我们在不断右移时知道仅剩下一位，那么右移次数即为答案，每次除以 2 后进行向下取整，相当于右移一位，那么由于前面在建表，也就是预处理，就已经求出来了，所以直接进行调用再加 1 即可。

查询步骤代码实现

int cx(int l,int r){
    int k=log2(r-l+1);
    return max(F[l][k],F[r-(1<<k)+1][k]);
}

整合代码

根据上述两步，那么我们可以得出下列代码，注意建表是需要把所有待处理的数输入好以后在进行建表。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int F[100005][25];
int a[100005];
int x,y;
void jb(){
    for(int i=1;i<=n;i++) F[i][0]=a[i];
    int k=log2(n);
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
        }
    }
} 
int cx(int l,int r){
    int k=log2(r-l+1);
    return max(F[l][k],F[r-(1<<k)+1][k]);
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    jb();
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        cout<<cx(x,y)<<endl;
    }
     return 0;
}

快读

但可以那份发现超时了，具体请见链接，那么我们可以发现，我们没法在该算法上的时间复杂度进行优化，只能在输入输出进行优化，由于题目所给的函数不会用，所以我将使用如下 3 行代码进行优化输入输出。

   ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

所以将这三行贴入那份代码,我们可以就可以通过本题了。务必要注意的是，需要在主函数的前三行去贴，才能保证每次输入均能被优化。这三行加入后，即可得到完美的正解。提示的已经很明显了。那么就可以得出如下代码。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int F[100005][25];
int a[100005];
int x,y;
void jb(){
    for(int i=1;i<=n;i++) F[i][0]=a[i];
    int k=log2(n);
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]);
        }
    }
} 
int cx(int l,int r){
    int k=log2(r-l+1);
    return max(F[l][k],F[r-(1<<k)+1][k]);
}
int main() {
 ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    jb();
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        cout<<cx(x,y)<<endl;
    }
     return 0;
}

ST 表补充说明

但是做 ST 表时，需要注意，就需要静态区间的，如果有变动，就非常占时间，因为动态可能导致数会发生变化，从而导致 ST 表需要重新建表，但因为题目说是静态区间的，所以可以使用 ST 表完成本题。