3285451_ac_32ms_484k.cpp

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

#include <stdio.h>
#include <algorithm>
#define max 10001

using namespace std;

struct node
{
	int l, r;

	bool operator < (const node &x)	const
	{
		if(l == x.l)
			return r < x.r;
		else
			return l < x.l;
	}
	bool operator == (const node &x)	const
	{
		return l == x.l && r == x.r;
	}
}s[max];

typedef struct NODE
{
	int L, R;
	int h;
	int l, r;
}Node;

int pos[10001];
Node root[50000];
int cnt, H;

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

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

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

	if(root[no].L==l&&root[no].R==r)
	{
		root[no].h++;
		return ;
	}
	mid = (root[no].L+root[no].R)/2;
	if(l > mid)
		insert(root[no].r,l,r);
	else
	{
		if(r <= mid)
			insert(root[no].l,l,r);
		else
		{
			insert(root[no].l,l,mid);
			insert(root[no].r,mid+1,r);
		}
	}
}

int find(int no,int p)
{
	int t, mid;

	t = root[no].h;
	if(root[no].L==root[no].R)
	{
		return t;
	}
	mid = (root[no].L+root[no].R)/2;
	if(p <= mid)
		return t+find(root[no].l,p);
	else
		return t+find(root[no].r,p);
}

int main()
{
	int i, n, l, r;

	scanf("%d%d%d%d",&n,&l,&H,&r);
	for(i = 0; i < r; i++)
	{
		scanf("%d%d",&s[i].l,&s[i].r);
		if(s[i].l > s[i].r)
		{
			swap(s[i].l,s[i].r);
		}
	}
	sort(s,s+r);
	creat_seg_tree(0,1,n);
	for(i = 0; i < r; i++)
	{
		if(s[i].l==s[i].r||s[i].l==s[i].r-1)
			continue;
		if(i&&s[i]==s[i-1])
			continue;
		insert(0,s[i].l+1,s[i].r-1);
	}
	for(i = 1; i <= n; i++)
	{
		printf("%d\n",H-find(0,i));
	}
	return 0;
}