n个人
他要插入的位置 和权值(这东西就最后输出来的)
倒的插就一定是他自己的位子
一个线段树维护一下就可以了
nlog(n)
#include<stdio.h>
#include<algorithm> using namespace std;
#define MAXN 200010
int z[MAXN],w[MAXN],ans[MAXN]; struct node
{
int l,r,si;
}x[MAXN<<]; void Build(int l,int r,int a)
{
x[a].l=l;
x[a].r=r;
x[a].si=r-l+;
if(l==r)
return ;
int mid=(l+r)>>;
Build(l,mid,a<<);
Build(mid+,r,a<<|);
} void Insert(int l,int r,int a1,int b1,int a)
{
if(l==r)
{
ans[l]=b1;
x[a].si--;
return ;
}
int mid=(l+r)>>;
if(a1<=x[a<<].si)
Insert(l,mid,a1,b1,a<<);
else
Insert(mid+,r,a1-x[a<<].si,b1,a<<|);
x[a].si--;
} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
scanf("%d%d",&z[i],&w[i]);
Build(,n,);
for(int i=n;i>=;i--)
Insert(,n,z[i]+,w[i],);
for(int i=;i<n;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
return ;
}