3146003_mle.c

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

#include <stdio.h>
#include <stdlib.h>
#define INIT (Node *)malloc(sizeof(Node))

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

Node *root;

Node *creat_seg_tree(Node *s,int l,int r)
{
	int mid;
	Node *p, *q;

	mid = (l+r)/2;
	s->L = l,s->R = r;
	if(l==r)
	{
		s->ll = s->rr = -1;
		s->l = NULL;
		s->r = NULL;
		return s;
	}
	p = INIT,q = INIT;
	s->ll = mid-l+1;
	s->rr = r-mid;
	s->l = creat_seg_tree(p,l,mid);
	s->r = creat_seg_tree(q,mid+1,r);
	return s;
}

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

int find(Node *t,int num)
{
	if(t->L==t->R)
		return t->L;
	if(t->ll >= num)
	{
		t->ll--;
		return find(t->l,num);
	}
	else
	{
		t->rr--;
		return find(t->r,num-t->ll);
	}
}

int main()
{
	int i;

	while(scanf("%d",&n)==1)
	{
		root = INIT;
		creat_seg_tree(root,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(root,pos[i]+1)] = val[i];
		}
		for(i = 0; i < n; i++)
		{
			printf("%d ",ans[i]);
		}
		printf("\n");
	}
	return 0;
}