244. 谜一样的牛

题意：有n只牛，现在他们按一种顺序排好，现在知道每只牛前面有几只牛比自己低，牛的身高是1-n，现在求每只牛的身高

解题思路：听了y总的课，他讲的是可以用树状数组+二分做，树状数组维护的是前i个比某头牛小的数量总和，初始状态下我们可以把每个高度都维护一下，千万不要跟我一样把tree数组一个一个变成1，那样是不行的，（没有理解树状数组的含义），简便方法就是tr[i]=lowbit(i),然后从后往前枚举，二分查找出第k+1矮的牛，搜索出来删去这头牛的身高，用ans数组存下每头牛的身高就行了。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const   int N=1e5+10;
int tr[N];
int a[N];
int ans[N];  
int n;
int lowbit(int x)
{
   
    return x&-x;
}
void add(int x)
{
   
    for(int i=x;i<=n;i+=lowbit(i))
    tr[i]--;
}
int sum(int x)
{
   
    int res=0;
    for(int i=x;i;i-=lowbit(i))
    res+=tr[i];
    return res;
}
int main()
{
   

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
   
        cout<<lowbit(i)<<endl;
    }
    for(int i=2;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=n;i>=1;i--)
    {
   
        int l=1,r=n;
        while(l<r)
        {
   
            int mid=l+r>>1;
            if(a[i]+1<=sum(mid))  r=mid;
            else    l=mid+1;
        }
        add(r);
        ans[i]=r;
    }
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<endl;
    return 0;
}