POJ 2828 Buy Tickets (想法题&后序插入&线段树下的二分查找)

http://poj.org/problem?id=2828

真是一道神题，朱泽园神牛出的。

首先用链表写的话常数太大（cache命中率太低了），会导致超时。

那怎么做？

注意到最后一个人的位置是确定的，再前一个人呢？他的位置即是空位的编号（对于第二组数据，倒数第二个人要在第1+1个空位，即第三个位置）

那我们怎么找到空位的编号呢？

用线段树维护区间的空位数，对于某人的所要插入的位置(或者说空位编号)，二分这颗线段树：

if (p <= empty[rt << 1]) return query(p, lson);
else return query(p - empty[rt << 1], rson);
           

这样，我们得到了一个O(nlogn)的算法，并且它是快于O(n)的链表算法的。

完整代码：

/*3297ms,4796KB*/

#include <cstdio>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 1, n, 1
const int mx = 200005;

int empty[mx << 2];
int pos[mx], val[mx], ans[mx];

void build(int l, int r, int rt)
{
	empty[rt] = r - l + 1;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}

int query(int p, int l, int r, int rt)
{
	--empty[rt];
	if (l == r) return l;
	int m = (l + r) >> 1;
	if (p <= empty[rt << 1]) return query(p, lson);
	else return query(p - empty[rt << 1], rson);
}

int main()
{
	int n, i, j, k;
	while (~scanf("%d", &n))
	{
		build(root);
		for (i = 1; i <= n; ++i)
			scanf("%d%d", &pos[i], &val[i]);
		///逆序插入
		for (i = n; i; --i)
			ans[query(pos[i] + 1, root)] = val[i];
		for (i = 1; i <= n; ++i)
			printf(i == n ? "%d\n" : "%d ", ans[i]);
	}
}