题目地址：http://poj.org/problem?id=2352
a[i]表示i排第几
每个位置i代表，1~i有几个比i小的数
可以从倒着来放数字，最后一个数n就是a[n]+1，因为只要前面有a[n]个比他小的数就好了，那么就是从小到大第a[n]个数
倒数第二个数也是这样，因为只要考虑在他前面的数
所以基本算法就是在待选的数中选第a[i]个放在i的位置上，当然要从后往前放
用树状数组+二分查找可以更快找出第a[i]个数
a[i]表示第i为放了没，所以一开始a[1~n]=1;
那么Sum(i)就表示1~i个数还有几个没放，即排第几
查出来后就将a[i]表示为0，表示已经用了
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=8000+5;
int lowbit[maxn],C[maxn],a[maxn],ans[maxn];
void init(int n)
{for(int i=1;i<=n;i++)lowbit[i]=i&(-i);
}
int Sum(int p) //a[1]+a[2]+....+a[p]
{int sum=0;while(p>0){sum+=C[p];p-=lowbit[p];}return sum;
}
void Modify(int p,int val,int n)
{while(p<=n){C[p]+=val;p+=lowbit[p];}
}
int BinarySearch(int v,int n) //查找第v的数
{int L=0,R=n;while(R-L>1) //1~n中选个排第v个的数字 {int mid=(L+R)/2;int p=Sum(mid); //Sum等于小于mid排第几在未用的数字中 if(p>=v) R=mid;else L=mid;}return R;
}
int main()
{int n;cin>>n;init(n);Modify(1,1,n);for(int i=2;i<=n;i++) cin>>a[i],Modify(i,1,n); //1~n 个数，每个位置待选 for(int i=n;i>=1;i--) {ans[i]=BinarySearch(a[i]+1,n); //查找第a[i]+1的数字 Modify(ans[i],-1,n); //标识用掉了 }for(int i=1;i<=n;i++) cout<<ans[i]<<endl;return 0;
}