Mayor's posters poj 2528

题目链接：http://poj.org/problem?id=2528

题目大意：贴海报，可以互相覆盖，问贴完所有海报最后能看到几张海报。

先离散化然后用线段树求解即可。

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=10300;

int X[maxn<<2];
int col[maxn<<4];
int li[maxn],ri[maxn];
bool hash[maxn];
int cnt;

void pushDown(int rt){
	if(col[rt]!=-1){
		col[rt<<1]=col[rt<<1|1]=col[rt];
		col[rt]=-1;
	}
}

int Bsearch(int key,int n,int X[]){//二分查找的模板 下标从0到n-1 查找不成功返回-1
	int l=0,r=n-1;
	while(l<=r){
		int m=(l+r)>>1;
		if(X[m]==key)return m;
		if(X[m]<key){
			l=m+1;
		}else{
			r=m-1;
		}
	}
	return -1;
}

void update(int L,int R,int c,int l,int r,int rt){
	if(L<=l && r<=R){
		col[rt]=c;
		return ;
	}
	pushDown(rt);//莫忘
	int m=(l+r)>>1;
	if(L<=m)update(L,R,c,lson);
	if(R>m)update(L,R,c,rson);
}

void query(int l,int r,int rt){
	if(col[rt]!=-1){
		if(!hash[col[rt]])cnt++;
		hash[col[rt]]=true;
		return ;
	}
	if(l==r)return ;
	int m=(l+r)>>1;
	query(lson);
	query(rson);
}

int main(){
	int t,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=0 ; i<n ; ++i){
			scanf("%d%d",&li[i],&ri[i]);
		}
		int nn=0;
		for(int i=0 ; i<n ; ++i){
			X[nn++]=li[i];
			X[nn++]=ri[i];
		}
		sort(X,X+nn);
		int m=1;
		for(int i=1;i<nn;++i){//去掉重复点
			if(X[i]!=X[i-1])X[m++]=X[i];
		}
		for(int i=m-1;i>=0;--i){//在数值上不相邻的点之间加上额外点
			if(X[i]!=X[i-1]+1)X[m++]=X[i-1]+1;
		}
		sort(X,X+m);
		memset(col,-1,sizeof(col));
		for(int i=0;i<n;++i){
			int l=Bsearch(li[i],m,X);
			int r=Bsearch(ri[i],m,X);
			update(l,r,i,0,m-1,1);
		}
		cnt=0;
		memset(hash,false,sizeof(hash));
		query(0,m-1,1);
		printf("%d\n",cnt);
	}
	return 0;
}