线段树练习题二

Description

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

Sample Input

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

Sample Output

4

Hint

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

解题思路

线段树
每种箱子为一种颜色，如：1,2,3,4……
区间初始颜色为0
如果这个区间有多种颜色就标记为-1
否则就标记为初始颜色或箱子颜***r> 线段树练习题一

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,s,f[1000005],cover[1000005];
void insert(int x,int l,int r,int a,int b,int num)
{
   
	if(cover[x]!=num)//线段树
	{
   
		int mid=(l+r)/2;
		if(l==a&&r==b)cover[x]=num;
		else
		{
   
			if(cover[x]>=0)//颜色
			{
   
				cover[x*2]=cover[x*2+1]=cover[x];
				cover[x]=-1;
			}
			if(b<=mid)insert(x*2,l,mid,a,b,num);
			else if(a>=mid)insert(x*2+1,mid,r,a,b,num);
			else
			{
   
				insert(x*2,l,mid,a,mid,num);
				insert(x*2+1,mid,r,mid,b,num);
			}
		}
	}
}
void sc(int x,int l,int r)//输出
{
   
	int mid=(l+r)/2;
	if(cover[x]>=0)f[cover[x]]=1;
	else if(l+1<r)
	{
   
		sc(x*2,l,mid);
		sc(x*2+1,mid,r);
	}
}
int main()
{
   
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
   
		int x,y;
		scanf("%d%d",&x,&y);
		insert(1,1,n,x,y,i);
	}
	sc(1,1,n);
	for(int i=1;i<=n;i++)//从1开始，初始颜色0不算看得到箱子
	 s+=f[i];//出现过则加加
	cout<<s; 
}

谢谢