【POJ】2182 - Lost Cows（线段树）

题目链接：点击打开链接

Lost Cows

Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands. Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow. Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N * Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5
1
2
1
0

Sample Output

2
4
5
3
1

Source

USACO 2003 U S Open Orange

从最后一个往前扫，线段树记录1~n未用数字的个数，区右区间的数字就行了。

代码如下：

#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAX 8000
#define L o<<1
#define R o<<1|1
struct node
{
	int l,r;
	int n;
}Tree[MAX << 2];

void PushUp(int o)
{
	Tree[o].n = Tree[L].n + Tree[R].n;
}

void Build(int o,int l,int r)
{
	Tree[o].l = l;
	Tree[o].r = r;
	if (l == r)
	{
		Tree[o].n = 1;
		return;
	}
	int mid = (l + r) >> 1;
	Build(L,l,mid);
	Build(R,mid+1,r);
	PushUp(o);
}

void Change(int o,int pos)
{
	if (Tree[o].l == Tree[o].r)
	{
		Tree[o].n = 0;
		return;
	}
	int mid = (Tree[o].l + Tree[o].r) >> 1;
	if (pos <= mid)
		Change(L,pos);
	else
		Change(R,pos);
	PushUp(o);
}

int Query(int o,int n)		//空穴数为n的右区间 
{
	if (Tree[o].l == Tree[o].r)
		return Tree[o].r;
	if (Tree[L].n >= n)
		return Query(L,n);
	else
		return Query(R,n-Tree[L].n);
}

int main()
{
	int n;
	scanf ("%d",&n);
	Build(1,1,n);		//创建线段树，表示空穴的个数 
	int a[MAX+5];
	for (int i = 2 ; i <= n ; i++)
		scanf ("%d",&a[i]);
	stack<int> s;
	s.push(a[n]+1);
	Change(1,a[n]+1);
	for (int i = n - 1 ; i > 1 ; i--)
	{
		int t = Query(1,a[i]+1);
		s.push(t);
		Change(1,t);
	}
	printf ("%d\n",Query(1,1));
	while (!s.empty())
	{
		printf ("%d\n",s.top());
		s.pop();
	}
	return 0;
}