node里储存剩余位置数

倒序更新

#include
    
     #include
     
      #include
      
       using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define mid (r+l)>>1const int maxn=200300;int node[maxn<<2],a[maxn],b[maxn],ans[maxn];void build(int l,int r,int rt){	node[rt]=r-l+1;	if(r==l)		return;	int m=mid;	build(lson);	build(rson);}void update(int n,int l,int r,int rt){	node[rt]--;	if(l==r)	{		ans[l]=b[n];		return;	}	int m=mid;	if(node[rt<<1]>=a[n])		update(n,lson);	else 	{		a[n]-=node[rt<<1];		update(n,rson);	}}void init(){	memset(a,0,sizeof(a));	memset(node,0,sizeof(node));	memset(b,0,sizeof(b));	memset(ans,0,sizeof(ans));}int main(){	int i,n;	while(scanf("%d",&n)!=EOF)	{		init();		for(i=1;i<=n;i++)		{			scanf("%d%d",&a[i],&b[i]);			a[i]++;		}		build(1,n,1);		for(i=n;i>=1;i--)		{			update(i,1,n,1);		}		printf("%d",ans[1]);		for(i=2;i<=n;i++)		{			printf(" %d",ans[i]);		}		printf("\n");	}	return 0;}