poj 2828 Buy Tickets (线段树单点更新，逆序插入)
题意：n个人，每个人有一个rp值（用来区分不同的人），还有一个pos[i]，表示当第i个人来排队的时候插入到第pos[i]个人的后面（也就是排在位置pos[i]+1)
现在问最后的序列，从1到n输出n个人的rp值
思路：第二道线段树，并不会做，看了题解。
比较关键的一点是：按照顺序的话，当后来的一个人插入到前面，那么之前很多人排好的位置将发生改变，这个代价是巨大的。
由于越后来的人越容易确定位置，因此正确的做法是倒序处理。
对于第i个人，我们把他放在从前往后数的第i个空的位置即可。
接下来需要做的就是线段树处理，线段树存储的信息是某一个区间中空位置的个数。
感觉是一道很好的题目，对于新手来说并不是很容易，不过理解了这道题目以后，感觉进一步理解线段树，有点开心。
/*************************************************************************
> File Name: code/poj/2828.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年10月29日 星期四 09时00分08秒
************************************************************************/
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<cctype>
#define yn hez111qqz
#define j1 cute111qqz
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
using namespace std;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
typedef long long LL;
typedef double DB;
const int inf = 0x3f3f3f3f;
const int N=2E5+7;
int pos[N],val[N];
int n;
int tree[N<<2]; //tree[i]存储的是以i为根节点的子树对应的区间中空位置的数量。
int ans[N];
void PushUp(int rt)
{
tree[rt] = tree[rt<<1]+tree[rt<<1|1]; //一段区间空位置的数量等于两端子区间中空位置的数量的和。
}
void build(int l,int r,int rt)
{
if (l==r)
{
tree[rt] = 1; //初始的空位置的数量为区间长度r-l+1
return ;
}
int m = (l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
void update (int p,int val,int l,int r,int rt)
{
if (l==r) //终于找到了该点的归属。。。
{
ans[l] = val;
tree[rt]--;
return ;
}
int m = (l+r)>>1;
if (p<=tree[rt<<1]) update(p,val,lson); //如果左子树所代表的区间中空位置的数目够的话就放左边
else update(p-tree[rt<<1],val,rson);//否则放右边，一共需要p个空位置，左边提供了tree[rt<<1]个，还需要右边提供p-tree[rt<<1]个。
PushUp(rt);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
while (~scanf("%d",&n))
{
for ( int i = 0 ; i < n ;i++) scanf("%d %d",&pos[i],&val[i]);
build(1,n,1);
for ( int i = n-1 ; i >= 0 ; i--)
{
pos[i]++;
update(pos[i],val[i],1,n,1);
}
for ( int i = 1 ; i <= n-1 ; i++) printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}