【線分樹】SSL_2646線分樹練習問題3

#include
int n,m,x,y,ans,z,f;
struct tr{
	int b,e,cover;
}tree[400001];
void creat(int p,int l,int r)
{
	tree[p].b=l;
	tree[p].e=r;
	if (r-l>1)
	{
		int m=(l+r)>>1;
		creat(2*p,l,m);
		creat(2*p+1,m,r);
	}
}
void insert(int p,int l,int r,int c)
{
	if (tree[p].cover!=c)//            ，            ，      
	{
		int m=(tree[p].b+tree[p].e)>>1;
		if (tree[p].b==l&&tree[p].e==r) tree[p].cover=c;
		else
		{
			if (tree[p].cover>=0)
			{
				tree[p*2].cover=tree[p*2+1].cover=tree[p].cover;
				tree[p].cover=-1;
			}
			if (r<=m) insert(2*p,l,r,c);
			else if (l>=m) insert(2*p+1,l,r,c);
			else
			{
				insert(2*p,l,m,c);
				insert(2*p+1,m,r,c);
			}
		}
	}
}
void count(int p)
{
	if (tree[p].cover>=0) 
	{
		if (tree[p].cover!=f)// f          ，          ，       ，    f
		{
			ans++;
			f=tree[p].cover;
		}
		return;
	}
	if (tree[p].e-tree[p].b>1)//           
	{
		count(p*2);
		count(p*2+1);
	}
}
void init()
{
	scanf("%d%d",&n,&m);
    creat(1,1,m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		insert(1,x,y,z);
	}
}
int main()
{
	init();
	count(1);
	printf("%d",ans);
}