POJ 2827 Buy Tickets（排隊問題，線段樹應用）

POJ 2827 Buy Tickets（排隊問題，線段樹應用）

ACM

題目地址：POJ 2827 Buy Tickets

題意：
排隊買票時候插隊。
給出一些數對，分別代表某個人的想要插入的位置Pos_i和他的Val_i，求出最後的隊列的val順序。

分析：
也是一道很巧妙的題目。
剛開始天真的以為sort一下就行了。wa了一發後發現我錯了...
原來可以很巧妙的用線段樹做。由於某個人想要插入posi位置，插入後他就在posi位置上了，但是可能其他人會插到他前面來，他的位置就會變成[在他後面且插在他位置及以前的人數]+posi了。
如果這樣就開始求了，當然用線段樹就可以做了，就跟求逆序數對一樣。
但是我們可以反著來考慮，只要從後面開始站，假設後面的人都已經站在正確的位置上了，那麼到那個人站的時候，現在的位置上已經都是後面的那些人了，只要數posi個空格，那那個人站的位置能確定了。確定之後就可以求下一個了，所以這個前提和結論都成立了。

所以我們只要從後面人站起，數posi個空格站上去就行了。
線段樹的話跟求和線段樹一樣，初始化時全部初始化為1，然後查找的時候可以“二分”查找，巧妙地找到需要的位置，具體見代碼，雖然代碼很挫。
代碼用了輸入輸出外掛來提速，沒加也能過的，請無視。

代碼：

/*
*  Author:      illuz 
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        2828.cpp
*  Create Date: 2014-08-05 20:16:28
*  Descripton:   
*/

#include 
#include 
#include 
#include 
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)

typedef long long ll;

const int N = 200000;
const int ROOT = 1;


// below is sement point updated version
struct seg {
	ll w;
};

struct segment_tree { 
	seg node[N << 2];

	void update(int pos) {
		node[pos].w = node[lson(pos)].w + node[rson(pos)].w;
	}

	void build(int l, int r, int pos) {
		if (l == r) {
			node[pos].w = 1;
			return;
		}
		int m = (l + r) >> 1;
		build(l, m, lson(pos));
		build(m + 1, r, rson(pos));
		update(pos);
	}

	int remove(int l, int r, int pos, ll x) {     // 刪掉並查詢
		if (l == r) {
			node[pos].w = 0;
			return l;
		}
		int m = (l + r) >> 1;
		int res;
		if (x < node[lson(pos)].w)      // 再此二分查找
			res = remove(l, m, lson(pos), x);
		else
			res = remove(m + 1, r, rson(pos), x - node[lson(pos)].w);
		update(pos);
		return res;
	}
} sgm;

int Scan() {
	int res = 0, ch, flag = 0;
	if((ch = getchar()) == '-')
		flag = 1;
	else if(ch >= '0' && ch <= '9')
		res = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9' )
		res = res * 10 + ch - '0';
	return flag ? -res : res;
}

void Out(int a) {
    if(a > 9)
        Out(a / 10);
    putchar(a % 10 + '0');
}

int a[2][N], n;
int ans[N];

int main() {
	while (~scanf("%d", &n)) {
		repf (i, 0, n - 1) {
			a[0][i] = Scan();
			a[1][i] = Scan();
		}
		sgm.build(1, n, ROOT);
		for (int i = n - 1; i >= 0; i--) {
			ans[sgm.remove(1, n, ROOT, a[0][i])] = a[1][i];
		}
		repf (i, 1, n) {
			if (i != 1)
				printf(" ");
			Out(ans[i]);
		}
		printf("\n");
	}
	return 0;
}