hihoCoder 1079 : 离散化（线段树之连续区间+离散化）经典题型

左手的ㄟ右手 2024-02-17 21:33 110阅读 0赞

#### \#1079 : 离散化 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

##### 描述 #####

小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~

这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？

于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间\[a\_i, b\_i\]表示，其中a\_i, b\_i均为属于\[0, L\]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？

[提示一：正确的认识信息量][Link 1]

[提示二：小Hi大讲堂之线段树的节点意义][Link 1]

##### 输入 #####

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。

每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a\_i, b\_i，表示第i张海报所贴的区间为\[a\_i, b\_i\]。

对于100%的数据，满足N<=10^5，L<=10^9，0<=a\_i<b\_i<=L。

##### 输出 #####

对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。

样例输入

5 10
    4 10
    0 2
    1 6
    5 9
    3 4

样例输出

分析：由于L较大，故需要离散化处理，具体处理见代码；

3 20
    1 10
    1 4
    6 10

应该输出的是3，但是直接做会输出2

1-4和6-10 这里用到了所有的离散后的数据1-2和3-4本来1-4和6-10中间还有4-6的部分是  
1-10这张的但1-2被改为2，3-4被改为3没有1了所以输出为2  
要是1-4后还有节点5的话就不会了至少节点5是1。

所以，我的离散化处理就是，先排序后，根据对应的位置，重新赋值，序列如1、3、5、7、9，中间空掉一位，来避免这种情况的发生！

![Center][]

AC代码：

#include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=1e5+10;
    int sum[maxn<<4];
    int vis[maxn*4];
    int A[maxn*2];
    int N,L;
    struct node{
    	int a,b;
    }nt[maxn];
    
    void pushDown(int rt){
         if(sum[rt]!=-1){
            sum[rt<<1]=sum[rt<<1|1]=sum[rt];
    	    sum[rt]=-1;
    	 }
    } 
    
    void update(int a,int b,int l,int r,int rt,int i){
    	if(a<=l&&b>=r){
    		sum[rt]=i;
    		return ;
        }
    
        if(r-l<=1)return ;   //当时这两条语句写反了导致RE了一次（数组越界） 
        pushDown(rt);
    		 
    	int m=l+(r-l)/2;
    	if(a<=m)
    	  update(a,b,l,m,rt<<1,i);
    	if(b>m)
    	  update(a,b,m,r,rt<<1|1,i);
    }
    
    void query(int l,int r,int rt,int& ans){
    	if(sum[rt]!=-1){
    		if(!vis[sum[rt]]){
    			vis[sum[rt]]=1;
    			ans++;
    		}
    		return ;
    	}
    	
    	if(r-l<=1)return ;
    	
    	int m=l+(r-l)/2;
    	query(l,m,rt<<1,ans);
    	query(m,r,rt<<1|1,ans);
    }
    
    int main(){
    	while(scanf("%d%d",&N,&L)==2){
    		int j=0;
    		for(int i=0;i<N;i++){
    		scanf("%d%d",&nt[i].a,&nt[i].b);
    		A[j++]=nt[i].a;
    		A[j++]=nt[i].b;
    	}
    	
    	sort(A,A+2*N);
    	//1、3、5、7..... 
    	for(int i=0;i<N;i++){  //离散化处理 
    		nt[i].a=2*(1+lower_bound(A,A+2*N,nt[i].a)-A)-1;
    		nt[i].b=2*(1+lower_bound(A,A+2*N,nt[i].b)-A)-1;
    	}
    
    	memset(sum,-1,sizeof(sum));
    	memset(vis,0,sizeof(vis));
    	
    	for(int i=0;i<N;i++){
    		update(nt[i].a,nt[i].b,1,4*N,1,i);
    	}
    	
    	int ans=0;
    	query(1,4*N,1,ans);
    	printf("%d\n",ans);
        }
    	return 0;
    }

[Link 1]: https://hihocoder.com/problemset/problem/1079#
[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/e709c416e31042a5b32c96e9fe571a79.png