ST表真的不能做吗

shoot_down @ 2023-09-25 21:38:59

#include<bits/stdc++.h>
using namespace std;
const int N=1e6*2+1;
int a[N],f[N][22],lg[N];
int n,m;
void init(){
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
    for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
}
int query(int l,int r){
    int k=lg[r-l+1];
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i][0]=a[i];
    }
    init();
    cout<<0<<endl;
    for(int i=2;i<=n;i++){
        if(i<=m) cout<<query(1,i-1)<<'\n';
        else cout<<query(i-m,i-1)<<'\n';
    }
    return 0;
}

by ran_qwq @ 2023-09-25 21:50:39

by diandian2020 @ 2023-09-25 21:58:08

直接对j这一维滚动就好了吧，因为对于 query(1,i-1) 一类的直接维护前缀min就好了；对于 query(i-m,i-1) 一类的，其实里面的 k=lg[r-l+1] 对于所有此类的 i 是定值，因为区间长度恒为 m，所以 st 表也只要算到这一维就行了

by diandian2020 @ 2023-09-25 22:04:45

刚写的：

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e6+9;
int n,m,k; 
int loggg[N],st[2][N];
void buildST(){
    for(int i=2;i<=n;i++) loggg[i]=loggg[i>>1]+1;
    k=loggg[m];
    for(int j=1;j<=k;j++)
        for(int i=1;i+(1<<j)<=n;i++)
            st[j&1][i]=min(st[j-1&1][i],st[j-1&1][i+(1<<j-1)]);
}
int query(int l,int r){
    return min(st[k&1][l],st[k&1][r-(1<<k)+1]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&st[0][i]);
    for(int i=1,mn=1e9;i<=m;i++){
        if(i==1) puts("0");
        else printf("%d\n",mn);
        mn=min(mn,st[0][i]);
    }//前一半直接统计前缀min 
    buildST();//后一半st表 
    for(int i=m+1;i<=n;i++) printf("%d\n",query(i-m,i-1));
    return 0;
}

by HEzzz @ 2023-09-29 21:49:08

@diandian2020 不对这不是也会MLE呀，你只也应该减不了你的空间复杂度

by diandian2020 @ 2023-09-30 14:50:51

@fengruijun 我空间复杂度是线性，怎么MLE了，不懂

by HEzzz @ 2023-09-30 15:25:15

@diandian2020 啊空间复杂度不是你数组的大小吗

by diandian2020 @ 2023-09-30 17:24:38

@fengruijun 您好好看看吧

by HEzzz @ 2023-09-30 18:23:08

@diandian2020 哦是我脑子短路了