线段树练习题三
Description
给定一条长度为m的线段,有n个操作,每个操作有3个数字x,y,z表示把区间[x,y]染成颜色z,询问染完色之后,这条长度为m的线段一共有几种颜色。规定:线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成多少段。
Sample Input
4 20 //四条,总长度为20
10 19 1
2 9 2
5 13 3
15 17 4
Sample Output
7
Hint
数据规模
N <= 10000
M <= 1000000
解题思路
AC代码
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,x,y,z,ans,a[4000010];
void insert(int dep,int l,int r,int x,int y,int color)//线段树
{
if(l==x&&r==y)
{
a[dep]=color;
return;
}
if(a[dep]>=0)
{
a[2*dep]=a[2*dep+1]=a[dep];
a[dep]=-1;
}
int mid=(l+r)/2;
if(y<=mid) insert(2*dep,l,mid,x,y,color);
else if(x>=mid) insert(2*dep+1,mid,r,x,y,color);
else
{
insert(2*dep,l,mid,x,mid,color);
insert(2*dep+1,mid,r,mid,y,color);
}
}
int find(int dep,int l,int r)//查找(输出)
{
int mid=(l+r)/2;
if(a[dep]>=0)
{
int s=1;
if(a[dep]==ans)
s=0;
ans=a[dep];
return s;
}
return find(dep*2,l,mid)+find(dep*2+1,mid,r);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
insert(1,1,m,x,y,z);
}
ans=-1;
printf("%d",find(1,1,m));
}