3146071_ac_1891ms_12056k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int L, R;
	int ll, rr;
	int l, r;
}Node;

Node root[500000];
int cnt;

void creat_seg_tree(int no,int l,int r)
{
	int mid;

	mid = (l+r)/2;
	root[no].L = l;
	root[no].R = r;
	if(l==r)
	{
		root[no].ll = root[no].rr = -1;
		root[no].l = -1;
		root[no].r = -1;
		return ;
	}
	root[no].ll = mid-l+1;
	root[no].rr = r-mid;
	root[no].l = ++cnt;
	creat_seg_tree(cnt,l,mid);
	root[no].r = ++cnt;
	creat_seg_tree(cnt,mid+1,r);
}

int n;
int val[200001], pos[200001];
int ans[200001];

int find(int no,int num)
{
	if(root[no].L==root[no].R)
		return root[no].L;
	if(root[no].ll >= num)
	{
		root[no].ll--;
		return find(root[no].l,num);
	}
	else
	{
		root[no].rr--;
		return find(root[no].r,num-root[no].ll);
	}
}

int main()
{
	int i;

	while(scanf("%d",&n)==1)
	{
		cnt = 0;
		creat_seg_tree(0,0,n-1);
		for(i = 0; i < n; i++)
		{
			scanf("%d%d",&pos[i],&val[i]);
		}
		for(i = n-1; i >= 0; i--)
		{
			ans[find(0,pos[i]+1)] = val[i];
		}
		for(i = 0; i < n; i++)
		{
			printf("%d ",ans[i]);
		}
		printf("\n");
	}
	return 0;
}