poj 2777 Count Color【线段树段更新】-蒲公英云

poj 2777 Count Color【线段树段更新】

题目：poj 2777 Count Color

题意：给出一段1 * n 的栅栏，有两种操作，第一种：把 l — r 全部染成同一颜色t，第二种，查询 l—-r 一共有多少种颜色。

分类：线段树

分析：我们可以给每个节点加一个标记，标记当前节点是否只有一种颜色，然后对只有一种颜色的节点如果要染色的话，那么他会变成几种颜色的，这时候记得向下更新一次就好，统计的时候统计节点有单个颜色的颜色就好。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 110000;
struct Node
{
    int l,r;
    long long num;
};
Node tree[4*N];
int vis[35];
void build(int l,int r,int o)
{
    tree[o].l=l;
    tree[o].r=r;
    tree[o].num=1;
    if(l==r)
        return ;
    int mid=(l+r)/2;
    build(l,mid,o*2);
    build(mid+1,r,o*2+1);
}
void update(int l,int r,int t,int o)
{
    if(tree[o].l==l && tree[o].r==r)
    {
        tree[o].num=t;
        return;
    }
    if(tree[o].num==t) return;
    if(tree[o].num!=-1)
    {
        tree[2*o].num=tree[o].num;
        tree[2*o+1].num=tree[o].num;
        tree[o].num=-1;
    }
    int mid=(tree[o].l+tree[o].r)>>1;
    if(r<=mid)
        update(l,r,t,o+o);
    else if(l>mid)
        update(l,r,t,o+o+1);
    else
    {
        update(l,mid,t,o*2);
        update(mid+1,r,t,o*2+1);
    }
}
void query(int l,int r,int o)
{
    if(tree[o].num!=-1)
    {
        vis[tree[o].num]=1;
        return ;
    }
    int mid=(tree[o].l+tree[o].r)>>1;
    if(r<=mid)
        query(l,r,o+o);
    else if(l>mid)
        query(l,r,o+o+1);
    else
    {
        query(l,mid,o*2);
        query(mid+1,r,o*2+1);
    }
}
int main()
{
    int n,c,m;
    while(~scanf("%d%d%d",&n,&c,&m))
    {
        build(1,n,1);
        while(m--)
        {
            getchar();
            char ok;
            int x,y,z;
            scanf("%c",&ok);
            if(ok=='C')
            {
                scanf("%d%d%d",&x,&y,&z);
                update(x,y,z,1);
            }
            else
            {
                int ans=0;
                memset(vis,0,sizeof(vis));
                scanf("%d%d",&x,&y);
                query(x,y,1);
                for(int i=1;i<=30;i++)
                    if(vis[i])
                        ans++;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}