题意就不说了,看图就明白了,就是问覆盖后,你能够看到多少张海报。

这个算是经典的离散化处理的线段树了,思路还是简单的。

离散化的想法是,将1-1000,1000-100000,只映射成为1-2,2-3两组线段。这样就合符空间复杂度了。

但是注意压缩的时候,对于两个离散化的点,如果不连续的时候,要插个板,否则那个结果并不是你期待的。

例如对于以下两组区间,如果不插板,得到的结果会是一样的:

1-5,6-10 1-5,7-10

如果不插板,一样的:

1-2,3-4

插板之后:

1-2,3-4 1-2,3,4-5
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 10101

int ans,bg[maxn],n,nd[maxn],hz,hashtable[maxn<<3],tmp[maxn<<3],poster[maxn<<4];
bool exist[maxn];

int hash(int point){
	int l=0,r=hz-1,m;
	while(l<=r){
		m=l+r >>1;
		if(hashtable[m]==point)return m;
		if(hashtable[m]>point){
			r=m-1;
		}else{
			l=m+1;
		}
	}
	return -1;
}

void update(int bg,int nd,int id,int l,int r,int root){
	if(bg<=l&&r<=nd){
		poster[root]=id;
		return ;
	}
	if(poster[root]!=-1){
		poster[root<<1]=poster[root<<1|1]=poster[root];
		poster[root]=-1;
	}
	int m=l+r >>1;
	if(bg<=m)update(bg,nd,id,l,m,root<<1);
	if(nd>m)update(bg,nd,id,m+1,r,root<<1|1);
}

void query(int l,int r,int root){
	if(poster[root]!=-1){
		if(!exist[poster[root]]){
			exist[poster[root]]=true;
			ans++;
		}
		return;
	}
	if(l==r)return;
	int m=l+r >>1;
	query(l,m,root<<1);
	query(m+1,r,root<<1|1);
}

int main(){
	int ts,cs,i,j;
	scanf("%d",&ts);
	for(cs=1;cs<=ts;cs++){
		scanf("%d",&n);
		for(j=i=0;i<n;i++){
			scanf("%d%d",&bg[i],&nd[i]);
			tmp[j++]=bg[i];
			tmp[j++]=nd[i];
		}
		sort(tmp,tmp+j);
		hashtable[hz=0]=tmp[0];
		for(i=1;i<j;i++){
			if(tmp[i]!=hashtable[hz]){
				if(tmp[i]!=hashtable[hz]+1){//本来不是连续的,就插个板将它们分开,否则离散化会出问题
					hashtable[hz+1]=hashtable[hz]+1;
					hz++;
				}
				hashtable[++hz]=tmp[i];
			}
		}
		hz++;
		memset(poster,-1,sizeof(int)*(hz<<2));
		for(i=0;i<n;i++){
			update(hash(bg[i]),hash(nd[i]),i,0,hz,1);
		}
		memset(exist,0,sizeof(int)*n);
		ans=0;
		query(0,hz,1);
		printf("%dn",ans);
	}
	return 0;
}