poj 2823セグメントツリー区間最値を求める
1610 ワード
poj 2823
#include<stdio.h>
#include<string.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 1001020
#define INF 1<<30
int min(int a,int b)
{
return a>b?b:a;
}
int max(int a,int b)
{
return a>b?a:b;
}
int n,k,h[2];
int da[maxn<<4],xiao[maxn<<4];
int ans1[maxn],ans2[maxn];
void PushUp(int rt)
{
da[rt]=max(da[rt<<1],da[rt<<1|1]);
xiao[rt]=min(xiao[rt<<1],xiao[rt<<1|1]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
scanf("%d",&da[rt]);
xiao[rt]=da[rt];
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
void query(int L,int R,int l,int r,int rt,int a[])
{
if(L<=l&&r<=R)
{
a[0]=max(da[rt],a[0]);
a[1]=min(xiao[rt],a[1]);
return ;
}
int m=(l+r)>>1;
int v=0;
if(L<=m)
query(L,R,lson,a);
if(R>m)
query(L,R,rson,a);
}
int main()
{
int i,j,k,l;
while(~scanf("%d %d",&n,&k))
{
build(1,n,1);
for(i=1;i<=n-k+1;i++)
{
h[0]=-INF;
h[1]=INF;
query(i,i+k-1,1,n,1,h);
ans1[i]=h[0];
ans2[i]=h[1];
}
for(i=1;i<=n-k+1;i++)
{
printf("%d ",ans2[i]);
}
printf("
");
for(i=1;i<=n-k+1;i++)
{
printf("%d ",ans1[i]);
}
printf("
");
}
return 0;
}