AcWing 244. 谜一样的牛
原题链接
简单
作者:
K.D.
,
2024-07-11 15:33:43
,
所有人可见
,
阅读 7
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int tr[N];
int ans[N];
int lowbit(int x)
{
return x & -x;
}
void update(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int query(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=2;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) update(i,1);
for(int i=n;i;i--){
int k = a[i] + 1;
int l = 1,r = n;
while(l < r){
int mid = l + r >> 1;
if(query(mid) >= k) r = mid;
else l = mid + 1;
}
ans[i] = l;
update(l,-1);
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}