题链：

题解：

线段树。

逆向考虑这个过程。最后的序列S共有n个元素。

先看最后一个人，如果他插入到第i位，那么他最终的位置就是当前序列S的第i号位置，然后把这个位置去掉，得到新序列S'。

再按上面的操作确定倒数第二个人的位置：

如果他插入到第j位，那么他就在新序列S'的第j个位置。

。。。。。。以此类推，可以确定出所有人的位置。

可以用线段树去确定位置。

代码：

#include
     
      #include
      
       #include
       
        #define MAXN 200050using namespace std;struct People{	int p,d;}P[MAXN];struct SGT{	int ls[MAXN<<1],rs[MAXN<<1],siz[MAXN<<1],sz,rt;	void build(int &u,int l,int r){		u=++sz; siz[u]=r-l+1;		if(l==r) return;		int mid=(l+r)/2;		build(ls[u],l,mid);		build(rs[u],mid+1,r);	}	void Reset(int n){		sz=rt=0;		build(rt,1,n);	}	int Modify(int u,int l,int r,int k){		siz[u]--; if(l==r) return l;		int mid=(l+r)/2;		if(k<=siz[ls[u]]) return Modify(ls[u],l,mid,k);		else return Modify(rs[u],mid+1,r,k-siz[ls[u]]);	}}DT;int ANS[MAXN];int main(){	int n;	while(~scanf("%d",&n)){		DT.Reset(n);		for(int i=1;i<=n;i++) scanf("%d%d",&P[i].p,&P[i].d);		for(int i=n,p;i;i--){			p=DT.Modify(DT.rt,1,n,P[i].p+1);			ANS[p]=P[i].d;		}		for(int i=1;i