比赛 树状数组练习 评测结果 AAAAAAA
题目名称 Lost Cows 最终得分 100
用户昵称 对立猫猫对立 运行时间 0.039 s
代码语言 C++ 内存使用 3.89 MiB
提交时间 2025-06-11 21:27:47
显示代码纯文本
#include <bits/stdc++.h>
#define Tairitsu return 0;
#define lowbit(x) (x & -x)
using namespace std;
int n, a[100001], st[100001], c[100001];
void add(int i, int x) {
	for (; i <= n; i += lowbit(i)) c[i] += x;
}
int ask(int i) {
	int t = 0;
	for (; i; i -= lowbit(i)) t += c[i];
	return t;
}
int main() {
	freopen("lostcows.in","r",stdin);
	freopen("lostcows.out","w",stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		add(i, 1);
	}
	for (int i = 2; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = n; i >= 1; i--) {
		int l = 1, r = n;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (ask(mid) > a[i]) r = mid - 1;
			else l = mid + 1;
		}
		st[i] = l;
		add(l, -1);
	}
	for (int i = 1; i <= n; i++) printf("%d\n", st[i]);
	Tairitsu
}