从后往前找,可以先确定最后一个牛的位置。
1. 从剩余的数中,找出第k小的数<=>等价于找到一个最小的x,st sum(x)=k
2. 删除某个数:add(x,-1)
如果前面有a[i]个比他矮,则排行应该是a[i]+1,因此二分的check点应该为sum(mid)>=a[i]+1
#include <iostream>
#include <cstring>
using namespace std;
const int N=100010;
int a[N],tr[N];
int res[N];
int n;
int lowbit(int x)
{
return x&-x;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
{
res+=tr[i];
}
return res;
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))
{
tr[i]+=c;
}
}
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
add(i,1);
}
int t=n+1;
for(int t=n;t>=1;t--)
{
int l,r;
l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
//如果前面有a[i]个比他矮,则排行应该是a[i]+1
//找到最小的x,满足sum(x)==a[t]+1
if(sum(mid)>=a[t]+1) r=mid;
else
l = mid+1;
}
res[t]=l;
add(l,-1);
}
for(int i=1;i<=n;i++)
{
cout<<res[i]<<endl;
}
return 0;
}