ST表 WA+RE60分

夜阑 @ 2022-08-04 09:02:39

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],l,r;
int f[100010][25],lg[100010];
int g[100010][25];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    lg[0]=-1;//lg[0]=-1,使lg[1]=0;
    for(int i=1;i<=n;i++){
        f[i][0]=a[i];//边界 
        g[i][0]=a[i];
        lg[i]=lg[i>>1]+1;//预处理logx 
    } 
    for(int j=1;j<=25;j++)//25=log100010 
        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]);
            g[i][j]=min(g[i][j-1],g[i+(1<<j-1)][j-1]);
        }
    for(int i=1;i+m-1<=n;i++){
        int l=i,r=i+m-1;
        int x=lg[r-l+1];
        cout<<min(g[l][x],g[r-(1<<x)+1][x])<<' ';
    }cout<<endl;
    for(int i=1;i+m-1<=n;i++){
        int l=i,r=i+m-1;
        int x=lg[r-l+1];
        cout<<max(f[l][x],f[r-(1<<x)+1][x])<<' ';
    }
    return 0;
}

by irris @ 2022-08-04 09:24:45

@夜阑 首先数据范围，其次这个题空间不是给 st 表用的。你可以试试四毛子。

by 夜阑 @ 2022-08-04 09:26:54

@AlgorithmerSnow 试试啥（疑惑

by Gumbo @ 2022-08-04 09:28:09

@夜阑 四毛子算法（自行bd）

by irris @ 2022-08-04 09:28:35

@夜阑 Method of Four Russians，可以做到 RMQ \mathcal O(n) 预处理 \mathcal O(1) 查询，空间复杂度线性。

by jor蛋 @ 2022-08-04 09:36:16

卡一个数组就能过

by jor蛋 @ 2022-08-04 09:41:36

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,l,r;
int f[N][22],lg[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>f[i][0];
    lg[0]=-1;//lg[0]=-1,使lg[1]=0;
    for(int i=1;i<=n;i++){
        lg[i]=lg[i>>1]+1;//预处理logx 
    } 
    for(int j=1;j<=21;j++)//25=log100010 
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    for(int i=1;i+m-1<=n;i++){
        int l=i,r=i+m-1;
        int x=lg[r-l+1];
        cout<<min(f[l][x],f[r-(1<<x)+1][x])<<' ';
    }cout<<endl;
    for(int j=1;j<=21;j++)//25=log100010 
        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-1<=n;i++){
        int l=i,r=i+m-1;
        int x=lg[r-l+1];
        cout<<max(f[l][x],f[r-(1<<x)+1][x])<<' ';
    }
    return 0;
}