AcWing 244. 谜一样的牛
原题链接
简单
作者:
NextAutumn
,
2025-01-13 15:41:05
,
所有人可见
,
阅读 4
//从后往前遍历,每次找出剩余排列中第ai + 1小的数字就是答案
//暴力做的话就是n^2,显然超时
//把每个数的使用次数用树状数组记录下来(初始化为1),那么第sum(i)必然是剩余中第i小的数字
//通过二分快速找到第ai + 1小的数字,再用sum(i)对比,就可以得出答案啦
#include<bits/stdc++.h>
#define lowbit(x) x & -x
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n;
int a[N], tr[N];
int ans[N];
void add(int id, int x)
{
for(int i = id; i <= n; i += lowbit(i)) tr[i] += x;
}
int sum(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for(int i = 2; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) add(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(sum(mid) >= k) r = mid;//找出第一个比ai+1小的数字
else l = mid + 1;
}
ans[i] = l;
add(l, -1);
}
for(int i = 1; i <= n; i ++) cout << ans[i] << '\n';
return 0;
}