线段树练习二 题解

线段树练习二

题目

桌子上零散地放着若干个不同颜色的盒子，桌子的后方是一堵墙。如右图所示。问从桌子前方可以看到多少个盒子？假设人站得足够远(输入时,由底向上,从左到右)。

样例

input
16 //桌子长度
5 // 盒子数量
4 7
12 14
1 5
6 10
11 16

output
4

数据范围

1<=$n$<=100000,1<=$m$<=100000,保证坐标范围为[1,$n$].

代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,ans,t[500020],f[100010];
void in(int d,int l,int r,int x,int y,int color)
{
	 int mid=(l+r)/2;
	 if (l==x&&r==y) //完全覆盖
	    t[d]=color;  //标记
	    else {
	    	if (t[d]>=1)
	    	{
	    		t[d*2]=t[d*2+1]=t[d];  //子节点先拿父节点的颜色
	    		t[d]=-1;  //标记不止一种颜色
	    	}
	    	if (x>=mid)  //继续搜
	    	   in(d*2+1,mid,r,x,y,color);
	    	   else if (y<=mid)
	    	           in(d*2,l,mid,x,y,color);
	    	           else {
	    	           	    in(d*2,l,mid,x,mid,color);
	    	           	    in(d*2+1,mid,r,mid,y,color);
	    	           }
	    }
}
void tj(int d,int l,int r)
{
	 int mid=(l+r)/2;
	 if (t[d]>0) 
	    f[t[d]]=1;  //标记
	    else if (r-l>1)  //继续搜
	            tj(d*2,l,mid),tj(d*2+1,mid,r);
} 
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		in(1,1,n,x,y,i);
	}
	tj(1,1,n);
	for (int i=1;i<=n;i++)
	    ans+=f[i];  //累加个数
	cout<<ans<<endl;
	return 0;
}