题目链接：https://vjudge.net/problem/POJ-2182

题意：有n头牛，从1..n编号，乱序排成一列，给出第2..n个牛其前面有多少比它编号小的个数，记为a[i]，求该序列的完整编号ans[i]。

思路：最近几天开始学线段树，加油！！我们从序列最后一个开始，则可以确定ans[n]=a[n]+1，然后把编号a[n]+1删除，继续判断倒数第二个...而这一求序列中第k小的数可通过线段树来完成。线段树结点包含l（区间左端点），r（区间右端点），len（区间剩余的编号个数）。每次查询时维护len属性，若k<=左子树的len，则遍历左子树，否则遍历右子树。

AC代码：

#include
     
      using namespace std;const int maxn=8005;struct node{    int l,r,len;}tr[4*maxn];int n,a[maxn],ans[maxn];void build(int v,int l,int r){    tr[v].l=l,tr[v].r=r,tr[v].len=r-l+1;    if(l==r) return;    int mid=(l+r)>>1;    build(2*v,l,mid);    build(2*v+1,mid+1,r);}int query(int v,int k){    --tr[v].len;    if(tr[v].l==tr[v].r) return tr[v].r;    if(k<=tr[2*v].len) query(2*v,k);    else query(2*v+1,k-tr[2*v].len);}int main(){    scanf("%d",&n);    for(int i=2;i<=n;++i)        scanf("%d",&a[i]);    build(1,1,n);    for(int i=n;i>=1;--i)        ans[i]=query(1,a[i]+1);    for(int i=1;i<=n;++i)        printf("%d\n",ans[i]);    return 0;}