SSL 2646_线段树练习题三_线段树

发布于 2019-05-20  8 次阅读


题目描述

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


思路

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


#include 
#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
]]>