线段树练习题二
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;
}