链接：http://poj.org/problem?id=2828
题意：n个人排队买票，按顺序输入n个人的插队信息，比如0，1，1，2这么输入，则第一个人站在第0个人身后，所以他是第一个人，第二个人站在第一个人身后，第三个人站在第一个人身后，此时之前的第二个人被往后挤了，变成了第三个人，而第三个战队的人站在了第二个位置，以此类推。
思路：这题最费时的就是更新数据部分了，以前见过这种题，当时奇葩的用链表写的，记得应该是T了，因为数据多了更新还是会很费时。没思路，看了别人的解题报告。
这题思路挺有意思的，从后往前排位置，因为越靠后的人位置越固定，靠前的人变动的可能更大。线段树维护剩余的空位数量。
插入位置pos值可以代表插入位置之前有几个人，拿这个和当前节点的左子树空余位置比，如果pos+1<=左子树空余位置，则说明插入位置之前的人和这个人本身都可以在左子树里容纳，，则把他添加到左子树中。否则说明当前插入的位置被之后插队的人占了，则把他添加到右子树中，并且插入位置变为pos-左子树空余位置，这样左子树空余位置越少，你要留出的空位就越多，所以，越靠后的人越先取位置，位置就越靠前。
语言表达能力有限，结合代码应该可以理解。
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 200010
#define eps 1e-7
#define INF 0x7FFFFFFF
#define ff sqrt(5.0)
typedef long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct node{
int pos,num;
}a[MAXN];
int sum[MAXN<<2];
int ans[MAXN];
void PushUP(int rt){
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
sum[rt] = 1;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUP(rt);
}
void query(int num,int pos,int l,int r,int rt){
sum[rt]--;
if(l==r){
ans[l] = num;
return ;
}
int m = (l + r) >> 1;
if(pos<=sum[rt<<1]) query(num,pos,lson);
else query(num,pos-sum[rt<<1],rson);
}
int main(){
int n,i;
while(scanf("%d",&n)!=EOF){
build(1,n,1);
for(i=0;i<n;i++) scanf("%d%d",&a[i].pos,&a[i].num);
for(i=n-1;i>=0;i--) query(a[i].num,a[i].pos+1,1,n,1);<span style="white-space:pre"> </span>//pos+1，空余位置要留给他之前的人，也要给他自己
for(i=1;i<n;i++) printf("%d ",ans[i]);
printf("%d\n",ans[i]);
}
return 0;
}