题目描述

给定一条长度为m的线段，有n个操作，每个操作有3个数字x,y,z表示把区间[x,y]染成颜色z，询问染完色之后，这条长度为m的线段一共有几种颜色。规定：线段的颜色可以相同。连续的相同颜色被视作一段。问x轴被分成多少段

思路

用一个c记录当前线段颜色，统计时判断子树的左右，若相同ans–

#include <stdio.h>
#define maxn 500005
struct tree
{
    int l,r,c;
}t[maxn];
int fl[maxn],lc=0,rc=0;
int insert(int f,int x,int y,int i)
{
    if (t[f].c!=i)
    {
        int m=(t[f].l+t[f].r)/2;
        if (t[f].l==x&&t[f].r==y) t[f].c=i;
        else
        {
            if (t[f].c>=0)
            {
                t[f*2].c=t[f*2+1].c=t[f].c;
                t[f].c=-1;
            }
            if (y<=m) insert(f*2,x,y,i);
            else if (x>=m) insert(f*2+1,x,y,i);
            else 
            {
                insert(f*2,x,m,i);
                insert(f*2+1,m,y,i);
            }
        }
    }
}
int ans;
int count(int p,int &lc,int &rc)
{
    int ff=0;
    int tl=0,tr=0;
    if (t[p].c>=0)
        {
            lc=rc=t[p].c;
            ff=1;
        }
    else if (t[p].r-t[p].l>1)
    {
        int l=count(p*2,lc,tl)+count(p*2+1,tr,rc);
        if (tl==tr&&tl>0) l--;
        ff=l; 
    }
    return ff;
}
int create(int f)
{
    if (t[f].r-t[f].l>1)
    {
        int m=(t[f].l+t[f].r)/2;
        t[f*2].l=t[f].l;
        t[f*2].r=m;
        t[f*2+1].l=m;
        t[f*2+1].r=t[f].r;
        create(f*2);
        create(f*2+1);
    }
}
int main()
{
  //  for (int i=0;i<maxn;i++) t[i].c=-1;
    int n,m;
    scanf("%d%d",&n,&m);
    t[1].l=1; t[1].r=m;
    create(1);
    for (int i=1;i<=n;i++)
    {
        int x,y,k;
        scanf("%d%d%d",&x,&y,&k);

        insert(1,x,y,k);
    }

    printf("%d\n",count(1,lc,rc));
}