POJ 2828 Buy Tickets（排队问题，线段树应用）

ACM

题目地址：

题意： 

排队买票时候插队。 

给出一些数对，分别代表某个人的想要插入的位置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 versionstruct 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;}