【POJ2182】Lost Cows

题面

vjudge

题解

从后往前做

每扫到一个点\(i\)以及比前面小的有\(a[i]\)个数

就是查询当前的第\(a[i]+1\)小

然后查询完将这个数删掉

两个操作可以用平衡树实现

但是我比较懒用了\(01trie\)

据说暴力也可以过

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

    return w * data;

}

const int MAX_N = 80005;

struct Trie { int ch[2], size; } t[MAX_N * 18]; int tot;

void insert(int v) {

	int o = 1; t[o].size++;

	for (int i = 17; i >= 0; i--) {

		int c = v >> i & 1;

		if (!t[o].ch[c]) t[o].ch[c] = ++tot;

		t[o = t[o].ch[c]].size++;

	}

}

void erase(int v) {

	int o = 1; t[o].size--;

	for (int i = 17; i >= 0; i--) {

		int c = v >> i & 1;

		t[o = t[o].ch[c]].size--;

	}

}

int Kth(int k) {

	int o = 1, res = 0;

	for (int i = 17; i >= 0; i--) {

		int sz = t[t[o].ch[0]].size;

		if (k <= sz) o = t[o].ch[0];

		else k -= sz, res |= 1 << i, o = t[o].ch[1];

	}

	return res;

}

int N, a[MAX_N], ans[MAX_N];

int main () {

	N = gi(); for (int i = 1; i < N; i++) a[i + 1] = gi(); ++tot;

	for (int i = 1; i <= N; i++) insert(i);

	for (int i = N; i >= 1; i--) {

		ans[i] = Kth(a[i] + 1);

		erase(ans[i]);

	}

	for (int i = 1; i <= N; i++) printf("%d\n", ans[i]);

    return 0;

}