[线段树]poj 2182

题意： 

       n头牛站队，每头牛都有一个属于[1,n]唯一的数字。对于每头牛，现在已知前面多少头牛的数字比他的大，问这n头牛的数字序列。

思路：

      和poj2828很相似，都是从后向前计算，建立一颗线段树，节点val值为，这个区间的空位数，然后从后向前更新线段树，也就是说，如果一个节点无法插入当前位置，那么就选择右侧最靠近这个节点的位置

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 8010;
struct{
    int l , r ,num;
}node[nMax*3];

int num[nMax] ,ans ,res[nMax];
void build(int l ,int r, int u){
    node[u].l = l;
    node[u].r = r;
    node[u].num = r - l + 1;
    if(l == r){
        return;
    }
    int m = (r + l)>>1;
    build(l , m , u*2);
    build(m + 1, r , u*2 + 1);
}

void update(int p ,int u){
    int l = node[u].l;
    int r = node[u].r;
    node[u].num -= 1;
    if(l == r){
        ans = r;
        return;
    }
    if(node[2*u].num >= p){
        update(p ,u*2);
    }else{
        p -= node[2*u].num;
        update(p ,u * 2 + 1);
    }
}
int main(){
    int n , i;
    while(scanf("%d",&n)!=EOF){
        for(i = 2 ;i <= n ;i++){
            scanf("%d",&num[i]);
            num[i] ++;
        }num[1] = 1;
        build(1 ,n ,1);
        for( i = n ; i >= 1; i--){
            update(num[i] ,1);
            res[i] = ans;
        }
        for(i = 1; i<= n; i++)
            printf("%d\n",res[i]);
    }
    return 0;
}