POJ 2182 Lost Cows (求序列第k大)

题解

二分+树状数组

显然最和一个数的值就是rank

那么其它数有什么规律？

从后往前匹配rank，我们可以发现第i个数的rank为还没有匹配的rank第(a[i]+1)大的数

这可以用 树状数组+二分 来求

一个数被选是0， 否则为1

显然sum(i) 表示第i个数前面有多少没被选的

二分找， 最小的i 使得 sum(i) == K

Code

#include<cstdio>
#define LL long long
#define RG register

using namespace std;

inline int gi() {
	RG int x = 0; RG char c = getchar(); bool f = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') c = getchar(), f = 1;
	while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();
	return f ? -x : x;
}
const int N = 80010;
int a[N], t[N], n;
#define lowbit(x) (x&(-x))
void add(int x, int k) {
	while (x <= n)
		t[x] += k, x += lowbit(x);
	return ;
}
inline int sum(int x) {
	int s = 0;
	while (x) s += t[x], x -= lowbit(x);
	return s;
}
int rank[N];
int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = gi();
	for (int i = 2; i <= n; i++) a[i] = gi();
	for (int i = 1; i <= n; i++)
		add(i, 1);
	for (int i = n; i; i--) {
		int l = 1, r = n;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (sum(mid) >= a[i]+1)
				r = mid-1;
			else l = mid+1;
		}
		rank[i] = r+1;
		add(r+1, -1);
	}
	for (int i = 1; i <= n; i++)
		printf("%d
", rank[i]);
	return 0;
}