wxyq @ 2021-08-01 12:37:52
#include<cstdio>
using namespace std;
const int M=1e6+1;
long long n,k,w[M],ma[M],mi[M],p=-0xfff,q=-0xfff,min_=0xffffffff,max_=-0xffffffff,l,r;
void xy(int t,int l,int r){
for(int t=l;t<=r;t++){
if(w[t] < min_){
min_ = w[t];
p=t;
}
}
mi[t]=min_;
min_=0xfffffff;
}
void yx(int u,int l,int r){
for(int u=l;u<=r;u++){
if(w[u] > max_){
max_ = w[u],
q=u;
}
}
ma[u]=max_;
max_=-0xfffffff;
}
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
l=1,r=k;
for(int i=1;i<=n;++i){
if( p < l )
xy(i,l,r);
else {
if(w[r] < w[p] )
mi[i]=w[r],p=r;
else mi[i]=w[p];
}
if( q < l )
yx(i,l,r);
else {
if(w[r] > w[q] )
ma[i]=w[r],q=r;
else ma[i]=w[q];
}
if(l < n-k+1)
++l,++r;
}
for(int i=1;i<=n-k+1;i++)
printf("%lld ",mi[i]);
printf("\n");
for(int i=1;i<=n-k+1;i++)
printf("%lld ",ma[i]);
return 0;
}by Chanter @ 2021-08-01 13:11:09
max取值小了
by wxyq @ 2021-08-07 09:53:48
@空与灵之白 啊？
by wxyq @ 2021-11-20 21:32:45
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,k,a[10000005],b[10000005],c[10000005],maxn=-0xfffff,minx=0xfffff;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline void build(int l,int r,int p){
if(l==r){b[p]=a[r],c[p]=a[r];return;}
int mid=(l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
b[p]=max(b[p<<1],b[p<<1|1]);
c[p]=min(c[p<<1],c[p<<1|1]);
}
inline int search(int l,int r,int tl,int tr,int p){
if(l>=tl && r<=tr){if(maxn < b[p]){
return b[p];}else return maxn;}
int mid=(l+r)>>1;
if(tl<=mid)maxn=search(l,mid,tl,tr,p<<1);
if(tr>mid)maxn=search(mid+1,r,tl,tr,p<<1|1);
return maxn;
}
inline int sea(int l,int r,int tl,int tr,int p){
if(l>=tl && r<=tr){if(minx>c[p]){return c[p];}else return minx;}
int mid=(l+r)>>1;
if(tl<=mid)minx=sea(l,mid,tl,tr,p<<1);
if(tr>mid)minx=sea(mid+1,r,tl,tr,p<<1|1);
return minx;
}
int main(){
n=read();
k=read();
for(int i=1;i<=n;i++)a[i]=read();
build(1,n,1);
for(int j=1;j<=n-k+1;j++){minx=0xfffff;printf("%d ",sea(1,n,j,j+k-1,1));}
printf("\n");
for(int j=1;j<=n-k+1;j++){maxn=-0xfffff;printf("%d ",search(1,n,j,j+k-1,1));}
return 0;
}/*8 3
1 3 -1 -3 5 3 6 7*/
//-1 -3 -3 -3 3 3
//3 3 5 5 6 7
by wxyq @ 2021-11-20 21:34:11
我用线段树还是 错 的