zoj 1610_Count the Colors_线段树

发布于 2019-05-14  5 次阅读


题目大意

在一条直线上进行涂色,每次涂色都会覆盖原有线段上的颜色,经过一系列涂色之后,求每种颜色分别覆盖了哪些线段。

思路

可以用线段树进行操作,加一个color,记录若当前区间被完全覆盖时的颜色,-1则为没有覆盖完,统计时将全部颜色打到一个桶里就可以了


#include 
struct tree
{
    int l,r,c;
}t[40001];
tree g[40001];
int fl[10001];
int te;
int build(int f)
{
    if (t[f].r-t[f].l==1) return 0;
    int m=(t[f].r+t[f].l)/2;
    t[f*2].r=m;
    t[f*2+1].l=m;
    t[f*2].l=t[f].l;
    t[f*2+1].r=t[f].r;
    t[f*2].c=-1;
    t[f*2+1].c=-1;
    build(f*2);
    build(f*2+1);
}
int insert(int f,int x,int y,int c)
{
    int m=(t[f].r+t[f].l)/2;
    if (t[f].c!=-1&&t[f].l+1!=t[f].r)
    {
        t[f*2].c=t[f].c;
        t[f*2+1].c=t[f].c;
    }
    if (t[f].l+1!=t[f].r) t[f].c=-1;
    if (t[f].l==x&&t[f].r==y)
        t[f].c=c;
    else if (x>=m) insert(f*2+1,x,y,c);
    else if (y<=m) insert(f*2,x,y,c);  
    else 
    {
        insert(f*2,x,m,c);
        insert(f*2+1,m,y,c);
    }
}
int count(int f)
{
    if (t[f].c!=-1)
    {
        if (te!=t[f].c)
        {
            fl[t[f].c]++;
            te=t[f].c;
        }
        return 0;
    }
    if (t[f].r-t[f].l!=1)
    {
        count(f*2);
        count(f*2+1);
    }
    else te=-1;
}
int main()
{
    int n;
    t[1].l=0;
    t[1].r=10000;
    t[1].c=-1;
    build(1);
    for (int i=0;i<=40000;i++)
    {
        g[i].l=t[i].l;
        g[i].c=t[i].c;
        g[i].r=t[i].r;
    }
    while (~scanf("%d",&n))
    {
        for (int i=1;i<=n;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            insert(1,x,y,z);
        }
        te=-1;
        count(1);
        for (int i=0;i<=8001;i++)
        {
            if (fl[i]!=0)
                printf("%d %d\n",i,fl[i]);
            fl[i]=0;
        }  
        printf("\n");
        for (int i=0;i<=40000;i++)
        {
            t[i].l=g[i].l;
            t[i].c=g[i].c;
            t[i].r=g[i].r;
        }
    }
}
]]>