poj 2528 Mayor's posters 线段树+离散化

离散化处理要注意+1（看了HH大牛的博客懂的，以前自己的代码是不对的）

例如数据：

1

3
1 10
1 3
6 10
这样，普通离散化处理  {1 3 6 10}， 然后此程序会操作成点染色，于是结果为2， 但正确答案为 3；
HH大牛给出一种离散化方法：
      如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了 (详见下面代码)按照上述方法离散化处理，为 {1 3 4 6 7 10 11 },  染色， 结果为 3；这样，就很简洁地将一个数字表示成一段区域。

#include<cstdio>
#include<cstdlib>
#include<cstring>
int seq[10010][2],ans;
bool visit[10010];

struct Line{
	int begin;
	int num;//表示其为第几张海报的首尾，首位负，尾为正
}line[20010];

struct Tree{
	int s;
	int t;
	int c;
}tree[140010];

int cmp(const void * a,const void *b){
	struct Line *aa=(struct Line *)	a;
	struct Line *bb=(struct Line *)	b;
	return aa->begin-bb->begin;
}

void build(int s,int t,int id){
	tree[id].s=s;
	tree[id].t=t;
	tree[id].c=0;
	if(s!=t){
		int mid=(tree[id].s+tree[id].t)>>1;
		build(s,mid,id*2);
		build(mid+1,t,id*2+1);
	}
}

void insert(int s,int t,int id,int colour){
	if(tree[id].s==s && tree[id].t==t){
		tree[id].c=colour;
		return ;
	}//否则的话从s到t的线段一定在tree[id]所表示的线段之内
	if(colour==tree[id].c)
		return ;

	if(tree[id].c>0){
		tree[id*2].c=tree[id].c;
		tree[id*2+1].c=tree[id].c;
	}
	int mid=(tree[id].s+tree[id].t)>>1;
	if(mid<s)
		insert(s,t,id*2+1,colour);
	else if(mid>=t)
		insert(s,t,id*2,colour);
	else{
		insert(s,mid,id*2,colour);
		insert(mid+1,t,id*2+1,colour);
	}
	if(tree[id*2+1].c!=tree[id*2].c || !tree[id*2+1].c || !tree[id*2].c)
		tree[id].c=0;
}

void search(int id){
	if(tree[id].c!=0){
		if(visit[tree[id].c]==false){
			ans++;
			visit[tree[id].c]=true;
		}
		return;
	}
	if(tree[id].s!=tree[id].t){
		search(id*2);
		search(id*2+1);
	}
}

int main(){
	int n,i,t,T;
	scanf("%d",&T);
	for(t=1;t<=T;t++){
		scanf("%d",&n);
		for(i=1;i<=n;i++){
			scanf("%d %d",&seq[i][0],&seq[i][1]);
			line[2*i-1].begin=seq[i][0];
			line[2*i-1].num=-i;
			line[2*i].begin=seq[i][1];
			line[2*i].num=i;
		}
		qsort(&line[1],2*n,sizeof(line[1]),cmp);

		int temp=line[1].begin,tp=1;  //这里去掉了重复的line
		for(i=1;i<=2*n;i++){
			if(line[i].begin!=temp){
				tp++;
				if(line[i].begin>temp+1)
					tp++;         //这个+1操作很重要
				temp=line[i].begin;
			}
			if(line[i].num<0)
				seq[-line[i].num][0]=tp;
			else
				seq[line[i].num][1]=tp;
		}//离散化

		build(1,tp,1);

		for(i=1;i<=n;i++){
			insert(seq[i][0],seq[i][1],1,i);
		}

		ans=0;
		memset(visit,false,sizeof(visit));
		search(1);
		printf("%d\n",ans);
	}
}