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]);
	}
}