题目链接：
https://cn.vjudge.net/problem/POJ-2828
题目大意：
插队的问题，每个案例给出n，代表有n个插队的，每个给出p,v，意思是代号为v的人插在了第p个人的后面，问最后的队伍的排列？
解题思路：
如果从前往后递推，每次插入在前面的话，后面的人都需要往后移动，所以考虑从后往前放
从后往前退的话每次可以推到确定的位置，插入在位置为i的地方，说明按从前往后放的时候前面有i个人，从后往前放的话就是前面有i个空格，放在第i+1个空格的地方，这样逆序放的话每次都可以放在确定的位置，不用移动。
线段树存的是区间内空格的数目，每次放的时候，位置需要加1，因为位置i说明放在前面有i个空格，该点在第i+1个空格处。
#include<iostream>
#include<cstdio>
#define MID(l, r) (l + (r - l) / 2)
#define lson(o) (o * 2)
#define rson(o) (o * 2 + 1)
using namespace std;
typedef long long ll;
const int INF = 1e9 +;
const int maxn = 1e6 + ;
int h, w, n;
struct node
{
int l, r, sum;
}tree[maxn];
int ans[maxn];
void build(int o, int l, int r)
{
tree[o].l = l, tree[o].r = r;
if(l == r)
{
tree[o].sum = ;
return;
}
int m = MID(l, r);
int lc = lson(o), rc = rson(o);
build(lc, l, m);
build(rc, m + , r);
tree[o].sum = tree[lc].sum + tree[rc].sum;
}
void insert(int o, int a, int b)//a个空位
{
if(tree[o].l == tree[o].r)
{
ans[tree[o].l] = b;
tree[o].sum = ;
return;
}
int lc = lson(o), rc = rson(o);
if(a <= tree[lc].sum)insert(lc, a, b);//空位数目小于等于左子树，在左子树中插入
else insert(rc, a - tree[lc].sum, b);//空位数目大于左子树，在右子树插入，此时a需要减去左子树的空位数目
tree[o].sum = tree[lc].sum + tree[rc].sum;//在插如之后空位数目发生变化，需要维护本节点的sum值
}
int a[maxn], b[maxn];
int main()
{
int n, m;
while(scanf("%d", &n) != EOF)
{
build(, , n);
for(int i = ; i < n; i++)scanf("%d%d", &a[i], &b[i]), a[i]++;//空位数目自加一，表示自己在第a[i]个空位处
for(int i = n - ; i >= ; i--)
{
insert(, a[i], b[i]);
}
for(int i = ; i < n; i++)printf("%d ", ans[i]);
printf("%d\n", ans[n]); }
return ;
}