ST表还可以优化成滚动数组吗?

P1440 求m区间内的最小值

Ly_boy @ 2022-10-29 10:59:34


#include <bits/stdc++.h>
using namespace std;

int read(){
    int x = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

int n,m,lg[2000005],st[2000005][21],x,y;
int query(int l,int r){
    if(l>r) return 0;
    int k = lg[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

int main(){
    n = read(),m = read();
    lg[1] = 0;
    for(int i=2;i<=n;i++)
        lg[i] = lg[i>>1]+1;

    for(int i=1;i<=n;i++)
        st[i][0] = read();

    for(int j=1;j<=lg[n];j++)
        for(int i=1;i<=n-(1<<j)+1;i++)
            st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

    printf("%d\n",0);
    for(int i=2;i<=n;i++){
        if(i-m<=0) x = 1;
        else x = i-m;
        y = i-1;
        printf("%d\n",query(x,y));
    }

    return 0;
}

by 鏡音リン @ 2022-10-29 11:04:46

可以啊(


by 鏡音リン @ 2022-10-29 11:04:56

因为这题区间长度固定


by yizhiming @ 2022-10-29 11:07:30

然而这道题区间长度可以和 n 同阶,数组大小还是没变(


by Ly_boy @ 2022-10-31 09:22:21

@鏡音リン 跪求大神代码,参考一下,总有几个点TML


by 鏡音リン @ 2022-10-31 09:52:42

@Ly_boy 我又没写过这种东西


|