Description
现在有n头牛，它们的编号1~n现在的排列是乱序的。只给出每一头牛的前面比它编号小的数量low，求确定每头牛的正确编号。
Sample Input
5
1
2
1
0
Sample Output
2
4
5
3
1
题解：
这题我写了暴力……交上去跑得很慢还居然过了，qwq但是课件里说这题是树状数组，那好吧再写一遍……
首先我们推一波样例，总共有5头牛，从第二头开始小于当前牛的数量依次是1，2，1，0。最后一头牛的地方是0，就是说所有的牛都比它高，那么这头牛编号一定是1。不难看出，最后一个位置的牛的low，决定了这头牛的编号为low+1。
我们可以根据这个规律来倒着找，从想法上来讲，是每次确定了一个牛以后，就在所有编号里删去这头牛的编号。这样每次都可以从最后一个位置找。
而又有一个事实：当前位置的牛，它的编号=前面小于它的数量+后面小于它的数量+1（我是从这里写的暴力）
我们可以用树状数组维护当前牛的前面比它小的数量。树状数组中的数组取0或者1，表示编号有没有被删。
前面小于它的数量=它的编号-后面小于它的数量-1
移项一下就不难看出来单调性了……（这里等式左边越大的话，表明等式右边的两个被减数越小，且减数越大）
所以我们可以开心地二分了。
当然用线段树呢是可以省一个log的复杂度的，因为线段树直接可以通过转移到左子树或右子树来实现二分。
（copy了老干部的板子）
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=10000; 5 int low[maxn]; 6 int h[maxn]; 7 int f[maxn]; 8 int n; 9 int lowbit(int x) 10 { 11 return(x&-x); 12 } 13 int get(int x)//查询前x项的和（有多少比i小） 14 { 15 int ret=0; 16 while(x) 17 { 18 ret+=f[x];//f[i]==0----当前数字被删，f[i]==1----当前数字可选 19 x-=lowbit(x); 20 } 21 return ret; 22 } 23 24 void add(int p,int c) 25 { 26 while(p<=n) 27 { 28 f[p]+=c; 29 p+=lowbit(p); 30 } 31 return; 32 } 33 34 int fin(int x) 35 { 36 int l=1,r=n,mid,s; 37 while(l<r) 38 { 39 mid=(l+r)>>1; 40 s=get(mid); 41 if(s>x) r=mid-1; 42 else if(s<x) 43 l=mid+1; 44 else 45 { 46 if(r==mid) 47 { 48 if(get(l)==x) 49 return l; 50 return r; 51 } 52 r=mid; 53 } 54 } 55 return l; 56 } 57 58 int main() 59 { 60 scanf("%d",&n); 61 add(1,1); 62 for(int i=2;i<=n;i++) 63 { 64 scanf("%d",&low[i]); 65 add(i,1); 66 } 67 for(int i=n;i;i--) 68 { 69 int k=fin(low[i]+1); 70 h[i]=k; 71 add(k,-1); 72 } 73 for(int i=1;i<=n;i++) 74 if(f[i]) 75 { 76 h[1]=f[i]; 77 break; 78 } 79 for(int i=1;i<=n;i++) 80 printf("%d ",h[i]); 81 return 0; 82 }