poj 2528 线段覆盖 线段树.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

//POJ 2528 线段覆盖 线段树
//注意 输入3 4，其实表示的是覆盖的线段从2到4，注意看图，被阴了。。。
#define NMAX 60000
#define MIN 0.000000001
#define PI 3.1415926535
typedef struct line
{
	int ll;
	int rr;
}line;

typedef struct tree
{
	int left;
	int right;
	int color;
}tree;

int lisan[NMAX*2];
line shuru[NMAX];
int temp[NMAX*2];
tree fun[NMAX*4];
int cc[NMAX];
int lsnum;

int cmpx(const void *a,const void *b)
{
	return (*(int *)a) - (*(int *)b);
}

int search(int key)
{
	int *p;
	p=(int *)bsearch(&key,lisan+1,lsnum,sizeof(int),cmpx);
	return (p-lisan);
}

void init(int num)
{
	int i,j;
	for(i=1,j=0;i<=num;i++)
	{
		temp[++j]=shuru[i].ll;
		temp[++j]=shuru[i].rr;
	}
	qsort(temp+1,num*2,sizeof(int),cmpx);
	lisan[1]=temp[1];
	for(i=2,j=1;i<=2*num;i++)
	{
		while(i<=2*num && temp[i]==temp[i-1]) i++;
		if(i <= 2*num) lisan[++j]=temp[i];
	}
	lsnum=j;
}

void create(int p,int l,int r)
{
	if(l==r) return;
	fun[p].left=l;
	fun[p].right=r;
	fun[p].color=0;
	if(r-l>1)
	{
		create(2*p,l,(l+r)/2);
		create(2*p+1,(l+r)/2,r);
	}
}

void insert(int p,int l,int r,int c)
{
	int mid=(fun[p].left+fun[p].right)/2;
	if(fun[p].color!=c)
	{
		if(l==fun[p].left && r==fun[p].right) fun[p].color=c;
		else
		{
			if(fun[p].color>0)
			{
				fun[2*p].color=fun[p].color;
				fun[2*p+1].color=fun[p].color;
			}
			fun[p].color=-1;
			if(r<=mid) insert(2*p,l,r,c);
			else if(l>=mid) insert(2*p+1,l,r,c);
			else 
			{
				insert(2*p,l,mid,c);
				insert(2*p+1,mid,r,c);
			}
		}
	}
}

void cal(int p)
{
	if(fun[p].color>0) cc[fun[p].color]++;
	else if(fun[p].color == -1)
	{
		cal(2*p);
		cal(2*p+1);
	}
}

int solve(int num)
{//广告个数
	int ans=0,a,b,i,tt;
	for(i=1;i<=num;i++) cc[i]=0;
	init(num);
	create(1,1,lsnum);
	for(i=1;i<=num;i++)
	{
		a=search(shuru[i].ll);
		b=search(shuru[i].rr);
		if(a!=b) 
		{
			if(a<b) insert(1,a,b,i);
			if(a>b) insert(1,b,a,i);
		}
	}
	cal(1);
	for(i=1;i<=num;i++)
		if(cc[i]>0) ans++;
	return ans;
}

int main()
{
	int num,nnum,i,j,a,b;
	scanf("%d",&nnum);
	for(i=1;i<=nnum;i++)
	{
		memset(lisan,0,sizeof(lisan));
		memset(temp,0,sizeof(temp));
		memset(cc,0,sizeof(cc));
		scanf("%d",&num);
		for(j=1;j<=num;j++)
		{
			scanf("%d %d",&a,&b);
			shuru[j].ll=a-1;
			shuru[j].rr=b;
		}
		printf("%d\n",solve(num));
	}
	return 0;
}