trouble_ @ 2018-03-09 18:25:58
#include<iostream>
#include<cstdio>
#define N 10000001
using namespace std;
int n,m;
int mmin,mmax;
int w[4*N],fm[4*N],fx[4*N];
int pushup1(int x)
{
fm[x]=min(fm[x<<1],fm[x<<1|1]);
}
int pushup2(int x)
{
fx[x]=max(fx[x<<1],fx[x<<1|1]);
}
void cc1(int l,int r,int x)
{
if(fm[x]!=0)
return;
if(l==r)
{
fm[x]=w[l];
return;
}
int mid=(l+r)>>1;
cc1(l,mid,x<<1);
cc1(mid+1,r,x<<1|1);
pushup1(x);
}
void cc2(int l,int r,int x)
{
if(fx[x]!=0)
return;
if(l==r)
{
fx[x]=w[l];
return;
}
int mid=(l+r)>>1;
cc2(l,mid,x<<1);
cc2(mid+1,r,x<<1|1);
pushup2(x);
}
int cz1(int L,int R,int l,int r,int x)
{
if(L<=l&&r<=R)
return fm[x];
int mid=(l+r)>>1;
if(L<=mid)
mmin=min(mmin,cz1(L,R,l,mid,x<<1));
if(R>mid)
mmin=min(mmin,cz1(L,R,mid+1,r,x<<1|1));
return mmin;
}
int cz2(int L,int R,int l,int r,int x)
{
if(L<=l&&r<=R)
return fx[x];
int mid=(l+r)>>1;
if(L<=mid)
mmax=max(mmax,cz2(L,R,l,mid,x<<1));
if(R>mid)
mmax=max(mmax,cz2(L,R,mid+1,r,x<<1|1));
return mmax;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
cc1(1,n,1);
cc2(1,n,1);
for(int i=1;i<=n-m+1;i++)
{
mmin=1234567809;
printf("%d ",cz1(i,i+m-1,1,n,1));
}
cout<<endl;
for(int i=1;i<=n-m+1;i++)
{
mmax=0;
printf("%d ",cz2(i,i+m-1,1,n,1));
}
}
by Iowa_BattleShip @ 2018-03-09 18:31:37
mmax初始化为极小值
by Iowa_BattleShip @ 2018-03-09 18:31:45
@trouble_
by trouble_ @ 2018-03-10 19:24:35
@Iowa_BattleShip 谢谢啦