2501747_ac_350ms_2692k.cpp

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

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

int n, lev[15001];
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);
}

int main()
{
	int i;
	int x, y;

	scanf("%d",&n);
	root = INIT;
	memset(lev,0,sizeof(lev));
	creat_seg_tree(root,0,32000);
	for(i = 0; i < n; i++)
	{
		scanf("%d%d",&x,&y);
		lev[find(root,0,x)]++;
		update(root,x);
	}
	for(i = 0; i < n; i++)
		printf("%d\n",lev[i]);
	return 0;
}