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