POJ 2828 Buy Tickets（排队问题，线段树应用）
ACM
题目地址：POJ 2828 Buy Tickets
题意：
排队买票时候插队。
给出一些数对，分别代表某个人的想要插入的位置Pos_i和他的Val_i，求出最后的队列的val顺序。
分析：
也是一道非常巧妙的题目。
刚開始天真的以为sort一下即可了。wa了一发后发现我错了...
原来能够非常巧妙的用线段树做。因为某个人想要插入posi位置，插入后他就在posi位置上了，可是可能其它人会插到他前面来，他的位置就会变成[在他后面且插在他位置及曾经的人数]+posi了。
假设这样就開始求了，当然用线段树就能够做了，就跟求逆序数对一样。
可是我们能够反着来考虑，仅仅要从后面開始站，如果后面的人都已经站在正确的位置上了，那么到那个人站的时候，如今的位置上已经都是后面的那些人了，仅仅要数posi个空格，那那个人站的位置能确定了。确定之后就能够求下一个了，所以这个前提和结论都成立了。
所以我们仅仅要从后面人站起，数posi个空格站上去即可了。
线段树的话跟求和线段树一样，初始化时所有初始化为1，然后查找的时候能够“二分”查找，巧妙地找到须要的位置，详细见代码，尽管代码非常挫。
代码用了输入输出外挂来提速，没加也能过的，请无视。
代码：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 2828.cpp
* Create Date: 2014-08-05 20:16:28
* Descripton:
*/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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;
}