poj 2528 线段树

这道题，咋一看，似乎非常简单。开个数组记录每个小格子的位置是被谁占用了即可。但是注意到， 1 <= i <= n, 1 <= l_i <= ri <= 10000000之后就会发现，开数组直接记录的方法虽然理论上可行，但是时间肯定不行。

然后想到用链表表示每一段：每一次插入的时候就更改一下链表，最后统计链表中的不同的poster的个数。但是这种效率是O(n^2),而且需要大量对链表的操作，时间效率也不高。

后来想到，把所有的li,ri排个序，然后就会大大压缩表示数组的长度，效率将会提高到O(n^2), n=10000. 这就是discuss里的称之为“离散化”的方法。

但是O(n^2)的方法，效率还是很低的。

然后在网上看了线段树的相关内容。

感觉：线段树通过完全树这种特殊的结构，就像是给最下面的各个段（也就是最终可能分成的段）建立了一个“索引”，而这个“索引”的查找效率是log(n)；因此把效率提高到O(nlog(n)).

通过hash和树对一些数据建立“索引”的方法是提高效率的利器。

浙江大学ACM程序设计竞赛培训，线段树

poj 2528代码：

/*
 * =====================================================================================
 *
 *       Filename:  2528.c
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2012年02月17日 16时43分28秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  MaZheng (blog.csdn.net/mazheng1989), [e-mail]
 *        Company:  Dalian University Of Technology
 *
 * =====================================================================================
 */


#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NUM_MAX 10000005
#define N_MAX 10005
//please declare parameters here.
struct Node{
	 int l;
	 int r;
	 int color;
}Tree[6*N_MAX];
struct Poster{
	int l;
	int r;
}posters[N_MAX];
int N;
int mapList[NUM_MAX];
int maxNum;//离散化之后的最大顶点号
 int rem[N_MAX];
 int cnt;//reslut
int cmp(const void *p1,const void *p2)
{
	int *num1=(int *)p1;
	int *num2=(int *)p2;
	return (*num1)-(*num2);
}
void Input(){
	memset(mapList,0,sizeof(mapList));
	maxNum=0;
	int i;
	for(i=0;i<N;i++)
	{
		scanf("%d %d",&posters[i].l,&posters[i].r);
		if(mapList[posters[i].l]==0)
		{
			mapList[posters[i].l]=1;
			rem[maxNum++]=posters[i].l;
		}
		if(mapList[posters[i].r]==0)
		{
			mapList[posters[i].r]=1;
			rem[maxNum++]=posters[i].r;
		}
	}
	//qsort rem[]
	qsort(rem,maxNum,sizeof(int),cmp);
	//create mapList
	for(i=0;i<maxNum;i++)
	{
		mapList[rem[i]]=i+1;
//		printf("%d %d\n",rem[i],i+1);
	}
}
void CreateLineTree(int sp,int tp,int p)
{
//	printf("maxNum==%d sp==%d tp==%d p==%d\n",maxNum,sp,tp,p);
	Tree[p].l=sp;
	Tree[p].r=tp;
	Tree[p].color=0;
	if(sp==tp)
		return ;
	int mid=(sp+tp)/2;
	CreateLineTree(sp,mid,p*2);
	CreateLineTree(mid+1,tp,p*2+1);
	return;
}
void Insert(int b,int e,int p,int color)
{
	if(e<Tree[p].l||b>Tree[p].r)
		return;
	if(b<=Tree[p].l&&e>=Tree[p].r)
	{
		Tree[p].color=color;
		return;
	}
	if(Tree[p].color>=0)
	{
		Tree[p<<1].color=Tree[(p<<1)+1].color=Tree[p].color;
		Tree[p].color=-1;
	}
	Insert(b,e,p<<1,color);
	Insert(b,e,(p<<1)+1,color);
}
char ColorFlag[N_MAX];
void Count(int p)
{
	if(Tree[p].color==0)
		return;
	if(Tree[p].color>0)
	{
		if(ColorFlag[Tree[p].color]==0)
		{
			ColorFlag[Tree[p].color]=1;
			cnt++;
		}
		return;
	}
	if(Tree[p].color<0)
	{
		Count(p<<1);
		Count((p<<1)+1);
	}
}
void Solve()
{
	Input();
	CreateLineTree(1,maxNum,1);
	int i;
	for(i=0;i<N;i++)
	{
		Insert(mapList[posters[i].l],mapList[posters[i].r],1,i+1);
	}
	memset(ColorFlag,0,sizeof(char)*(maxNum+1));
	cnt=0;
	Count(1);
	printf("%d\n",cnt);
}
//please declare functions here.

int main()
{
	 if(freopen("input.txt","r",stdin)==NULL) perror("Can not open the input file!");
	 
	//input your ...
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		Solve();
	}

	return 0;
}