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; }