学步园

题意:

插队

posi    vali

编号为vali的人插在posi位置的人身后.

输出最终队伍.

/**
此题的关键在于逆序循环!
对于插队这项活动,总是越靠后越方便夺取胜利果实...
倒着循环,那么每次取的人的位置都能直接确定.
位于当前人的位置pos[i]+1,他的前面(截止到他来的时候)必然有pos[i]个人,而这pos[i]个人
一定是倒序循环尚且没有涉及的.因此要在当前人的前面留下pos[i]个位置(*).
已经被占了位置的是"未来"的事,所以对于pos[i]长的队来说并不存在.而倒着循环的时候
连续的队伍就变成了"找空位".
**/
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define REP(i,n) for(int i=0;i<(n);++i)//全部循环
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)//区间升序循环
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)//区间降序循环

#define lson l,m,rt<<1  // 左儿子
#define rson m+1,r,rt<<1 | 1 // 右儿子
// rt即为root，表示当前子树的根

#define N 200010

int tree[N<<2];
int val[N],pos[N],ans[N];
int id;
void build(int l,int r,int rt)
{
    tree[rt]=r-l+1;//含端点的区间内空位个数,初始化为全空
    if(l==r)    return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
}
void update(int p,int l,int r,int rt)
{
    tree[rt]--;//插入了一个节点,那么一路找下来每个节点空位数都-1
    if(l==r)
    {
        id=l;//如果找到了叶子节点,则将插入的位置存在id中;返回
        return;
    }
    int m=(l+r)>>1;//选择中点
    if(tree[rt<<1]>=p) update(p,lson);//如果左儿子的空位数足以容纳
    //当前的人和他前面的所有人,则将当前人插入左儿子
    else
    {//否则,更新右儿子.此时插入的人相对于右儿子的位置变成p-=tree[rt<<1];
    //即是把左儿子的空余区间长度
        p-=tree[rt<<1];
        update(p,rson);
    }
}
int main(void)
{
    int n;
    while(scanf("%d",&n)==1)
    {
        build(1,n,1);//从1到n建树,n为队伍长度
        FOR(i,1,n)  scanf("%d%d",pos+i,val+i);//存在两个数组里
        FORD(i,n,1)//插在posi的后面,那么此人当前位置pos[i]+1
        {///逆!!序!!循!!环!!
            update(pos[i]+1,1,n,1);
            ans[id]=val[i];//节点插入的位置id就是最终的队列位置
        }
        FOR(i,1,n)  printf("%d%c",ans[i],i==n?'\n':' ');
    }
    return 0;
}