为什么我开两个st表过了?

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

Liuliwei123 @ 2024-08-26 21:46:10

听题解的大神们说,开两个st表会 MLE ,但为什么我过了?过得还挺轻松,时间最高600+ms,关O2,700+ms

下面是代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+8;
int mx[N][20],mn[N][20],n,k;
void init(){
    int r=log2(k);
    for(int i=1;i<=r;i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
            mn[j][i]=min(mn[j][i-1],mn[j+(1<<(i-1))][i-1]);
        }
    }
}
int fmin(int a,int b){
    int r=log2(b-a+1);
    int minn=min(mn[a][r],mn[b-(1<<r)+1][r]);
    return minn;
}
int fmax(int a,int b){
    int r=log2(b-a+1);
    int maxx=max(mx[a][r],mx[b-(1<<r)+1][r]);
    return maxx;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>mx[i][0];
        mn[i][0]=mx[i][0];
    }
    init();
    for(int i=1;i+k-1<=n;i++){
        cout<<fmin(i,i+k-1)<<" ";
    }
    cout<<endl;
    for(int i=1;i+k-1<=n;i++){
        cout<<fmax(i,i+k-1)<<" ";
    }
    return 0;
}

by tin_ingot @ 2024-08-26 21:53:41

是的,之前我用st过了400ms的滑动窗口,只要数组开的合理就没事。


|