AcWing 244. 谜一样的牛
原题链接
简单
作者:
知恩海
,
2024-05-19 16:13:50
,
所有人可见
,
阅读 4
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int tr[N];
int n,m;
int h[N];
int ans[N];
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;
}
signed main()
{
cin >> n ;
for(int i = 2 ;i <= n;i++) cin >> h[i];
for(int i = 1; i<= n;i++) tr[i] = lowbit(i);
for(int i = n ; i ; i--){//从后往前看 每次最后的那个数 本来就是确定 大小的 那么每次处理完 都把最后一个数去掉就行
int k = h[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;
}
add(l, -1);//那个数已经使用过了 可以删除
ans[i] = l;
}
for(int i =1;i<=n;i++)cout << ans[i] << endl;
}