线段树练习题一

Description

桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

Sample Input

20 //桌面总宽度
4 //盒子数量
1 5
3 8
7 10
13 19

Sample Output

15

Hint

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

解题思路

线段树

线段树练习题一（离散化）

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,x,y,s,cover[1000005];
void insert(int x,int l,int r,int a,int b)//线段树
{
   
	int mid=(l+r)/2;
	if(cover[x]==1)return;//如果已经被覆盖就直接返回
	if(l==a&&r==b){
   cover[x]=1;return;}//如果刚好覆盖这个区间就标记
	if(b<=mid)insert(x*2,l,mid,a,b);
	else if(a>=mid)insert(x*2+1,mid,r,a,b);
	else
	{
   
		insert(x*2,l,mid,a,mid);
		insert(x*2+1,mid,r,mid,b);	
	}
}
void sc(int x,int l,int r)//输出
{
   
	int mid=(l+r)/2;
	if(cover[x]==1)//如果被覆盖就加
	{
   
		s+=r-l;
		return;
	}
	if(r-l>1)
	{
   
		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++)
	{
   
		scanf("%d%d",&x,&y);
		insert(1,1,n,x,y);
	}
	sc(1,1,n);
	cout<<s;
}

谢谢