Lost Cow

题意：有n头牛，每头牛都有自己的编号，给你n-1个数，从第二头牛开始，表示第i头牛之前比第i头牛编号小的有几个，然后求出每头牛的编号。


代码参考 《算法竞赛从入门到进阶》
最初不太理解findpos（）和add(x,-1)什么意思，现在好像稍微懂了点（见注释），先把现在理解的记录一下。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#define ll long long
#define lowbit(x) ((~x+1)&x)
using namespace std;
const int N = 1e3+10;
int n,m,tree[N],a[N];
int pre[N];void add(int x,int d) {while(x<=n) {tree[x]+=d;x+=lowbit(x);}
}int sum(int x) {int sum=0;while(x>0) {sum+=tree[x];x-=lowbit(x);}return sum;
}int findpos(int x) {int l=1,r=n;while(l<r) {int mid = (l+r)>>1;if(sum(mid)<x) l=mid+1;else r = mid;}return l;
}int main() {cin>>n;int ans[N];pre[1] = 0;for(int i=2; i<=n; i++) {cin>>pre[i];}for(int i=1; i<=n; i++) {tree[i] = lowbit(i);}for(int i=n; i>0; i--) {int x = findpos(pre[i]+1);//找到某个数x，使得tree[x]==pre[i]+1,表示x之前比x大的数有pre[i]+1个，pre加一是因为tree是从1开始包括自己本身add(x,-1);//tree-1表示x从1-n中去除，相当于没有了x编号//例如 输入5 1 2 1 0，从i=n开始1之前比1小的有1个（本身），所以最后一个就是1，就把1从1-5中去掉，2之前比2晓得就只有本身，所以tree[2]--，3之前比3小的就只有2,3，tree[3]--;ans[i] = x;}for(int i=1; i<=n; i++) {cout<<ans[i]<<endl;}return 0;
}