树状数组维护剩余使用次数的前缀和

每头牛前面有k头比他矮的牛，也就是每次在剩余的数字中寻找第k小的数。

#include<iostream>
using namespace std;
const int N=1e5+10;

int tr[N];

int n;
int h[N],p[N]; // h是身高，p是关系

int lowbit(int x)
{
    return x&-x;
}

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    cin>>n;
    for(int i=2;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) tr[i]=lowbit(i); //等价于添加
    //for(int i=1;i<=n;i++) add(i,1);
    for(int i=n;i;i--)
    {
        int k=p[i]+1;

        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(sum(mid)>=k) r=mid;
            else l=mid+1;
        }

        h[i]=r;
        add(r,-1); //已经使用过了，标记掉
    }

    for(int i=1;i<=n;i++) cout<<h[i]<<endl;
    return 0;
}