st表求调

P1886 滑动窗口 /【模板】单调队列

microchip @ 2023-06-27 16:35:24

尝试用st表，一开始用cin和cout导致3个点1.01s超时

然后试了试用scanf和printf，就RE了

如果不是越界，还有什么问题呢

如果你建议我用单调队列......我不会QAQ

代码：

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

int n,k,a[1000050],st[1000050][20],LOG[1000050];

int pow(int A,int B){
    int ret=1;
    while(B--){
        ret*=A;
    }return ret;
}

int find_min(int A,int B){
    return min(st[A][LOG[B-A+1]],st[B-pow(2,LOG[B-A+1])+1][LOG[B-A+1]]);
}

int find_max(int A,int B){
    return max(st[A][LOG[B-A+1]],st[B-pow(2,LOG[B-A+1])+1][LOG[B-A+1]]);
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=log2(n);j++){
            st[i][j]=99999999;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        st[i][0]=a[i];
        LOG[i]=log2(i);
    }for(int j=1;j<=LOG[n];j++)
        for(int i=1;i<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+pow(2,j-1)][j-1]);
    for(int i=1;i<=n-k+1;i++){
        cout<<find_min(i,i+k-1)<<' ';
    }cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=log2(n);j++){
            st[i][j]=-99999999;
        }
    }for(int i=1;i<=n;i++){
        st[i][0]=a[i];
    }for(int j=1;j<=LOG[n];j++)
        for(int i=1;i<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+pow(2,j-1)][j-1]);
    for(int i=1;i<=n-k+1;i++){
        cout<<find_max(i,i+k-1)<<' ';
    }
    return 0;
}

by microchip @ 2023-06-27 16:35:48

不过最后用线段树过了，线段树yyds

by Rosaya @ 2023-06-27 16:41:10

你这 pow 也太慢了。

by Neutralized @ 2023-06-27 16:48:39

今天第一次见到了 O(\log n) 查询的 ST 表

by stntn @ 2023-06-27 16:50:56

今天第一次见到了 O(\log n) 查询的 ST 表

by microchip @ 2023-06-27 17:07:35

@Rosaya 谢谢，但是似乎并不是pow的问题

我把所有pow换成位运算了不过还是RE

by Rosaya @ 2023-06-27 17:09:59

@microchip 你能不能把你 scanf 和 printf 的代码发出来，我猜你用错了。

by microchip @ 2023-06-27 17:11:35

@Rosaya 这个

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

int n,k,a[1000050],st[1000050][20],LOG[1000050];

int find_min(int A,int B){
    return min(st[A][LOG[B-A+1]],st[B-(1<<LOG[B-A+1])+1][LOG[B-A+1]]);
}

int find_max(int A,int B){
    return max(st[A][LOG[B-A+1]],st[B-(1<<LOG[B-A+1])+1][LOG[B-A+1]]);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=log2(n);j++){
            st[i][j]=99999999;
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        st[i][0]=a[i];
        LOG[i]=log2(i);
    }for(int j=1;j<=LOG[n];j++)
        for(int i=1;i<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n-k+1;i++){
        cout<<find_min(i,i+k-1)<<' ';
    }cout<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=log2(n);j++){
            st[i][j]=-99999999;
        }
    }for(int i=1;i<=n;i++){
        st[i][0]=a[i];
    }for(int j=1;j<=LOG[n];j++)
        for(int i=1;i<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n-k+1;i++){
        cout<<find_max(i,i+k-1)<<' ';
    }
    return 0;
}

by Rosaya @ 2023-06-27 17:14:10

@microchip st[1+(1<<j-1)][j-1] 越界了。

by microchip @ 2023-06-27 17:21:13

@Rosaya 谢谢 orz

by microchip @ 2023-06-27 17:22:06

不过st表好像有点慢，~~吸氧才A的~~

| 下一页