学步园

题目

和poj 2828差不多的意思

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxn 8010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct Tree
{
    int l,r,num;
}tree[maxn<<2];

int p[maxn],ans[maxn];

void build(int l,int r,int rt)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].num=r-l+1;
    if(tree[rt].l==tree[rt].r) return ;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}

int query(int pos,int rt)
{
    int l,r;
    l=tree[rt].l;
    r=tree[rt].r;
    tree[rt].num--;
    if(l==r) return l;
    if(pos<=tree[rt<<1].num)
       return query(pos,rt<<1);
    else{
        return query(pos-tree[rt<<1].num,rt<<1|1);
    }
}

int main()
{
    int i,n;
    while(~scanf("%d",&n)){
        build(1,n,1);
        p[1]=0;
        for(i=2;i<=n;i++){
            scanf("%d",&p[i]);
        }
        for(i=n;i>=1;i--){
            ans[i]=query(p[i]+1,1);
        }
        for(i=1;i<=n;i++){
            printf("%d\n",ans[i]);
        }
        return 0;
    }
    return 0;
}