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的滑动窗口,只要数组开的合理就没事。