3090274_ac_1812ms_39400k.cc

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

#include <stdio.h>
#include <algorithm>
#define INIT (seg_tree *)malloc(sizeof(seg_tree))

using namespace std;

struct node
{
	int id;
	int x, y;
}itv[100001];

int n, lev[100001];
typedef struct seg_tree
{
	int num;
	int L, R;
	struct seg_tree *l, *r;
}seg_tree;

seg_tree *root;

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

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

int find(seg_tree *s,int l,int r)
{
	int mid;

	if(s->L==l&&s->R==r)
		return s->num;
	mid = (s->L+s->R)/2;
	if(l>mid)
		return find(s->r,l,r);
	else
		if(r<=mid)
			return find(s->l,l,r);
	return find(s->l,l,mid)+find(s->r,mid+1,r);
}

void update(seg_tree *s,int x)
{
	int mid;

	if(x<=s->R&&x>=s->L)
		s->num++;
	if(s->L==s->R)
		return ;
	mid = (s->L+s->R)/2;
	if(x<=mid)
		update(s->l,x);
	else
		update(s->r,x);
}


bool cmp(node a,node b)
{
	if(a.x == b.x)
		return a.y > b.y;
	else
		return a.x < b.x;
}

int main()
{
	int i;

	while(scanf("%d",&n),n)
	{
		root = INIT;
		memset(lev,0,sizeof(lev));
		creat_seg_tree(root,0,100000);
		for(i = 0; i < n; i++)
		{
			scanf("%d%d",&itv[i].x,&itv[i].y);
			itv[i].id = i;
		}
		sort(itv,itv+n,cmp);
		for(i = 0; i < n; i++)
		{
			if(i&&itv[i].x==itv[i-1].x&&itv[i].y==itv[i-1].y)
			{
				lev[itv[i].id] = lev[itv[i-1].id];
				update(root,itv[i].y);
				continue;
			}
			lev[itv[i].id] = find(root,itv[i].y,100000);
			update(root,itv[i].y);
		}
		for(i = 0; i < n; i++)
		{
			printf("%d ",lev[i]);
		}
		printf("\n");
	}
	return 0;
}