POJ 2777 Count Color （线段树的区间更新+lazy tag）

淩亂°似流年 2022-06-13 13:47 176阅读 0赞

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.  
  
There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:  
  
1. "C A B C" Color the board from segment A to segment B with color C.  
2. "P A B" Output the number of different colors painted between segment A and segment B (including).  
  
In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample Input

2 2 4
    C 1 1 2
    P 1 2
    C 2 2 2
    P 1 2

Sample Output

2
    1

题解：

一开始搜了很多题解，说是要用进制来保存状态，一看这题最多有32种颜色，2的32次方。。数组早爆炸了，用多个数组有点麻烦，然后就找到了一个神犇的博客没用lazy tag写的，不是很熟哦线段树的我照着他的博客以我的方格打了一遍，把我的注释打了上去，原博客：http://www.2cto.com/kf/201512/454627.html

代码：

#include<stdio.h>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<queue>
    #include<stack>
    #include<map>
    using namespace std;
    const int MAX=1e5+5;
    int vis[35];//颜色的访问数组
    struct node
    {
        int l,r;
        int color;//记录区间内的颜色，如果颜色为多种则为-1
    }t[MAX*4];
    int L,m,n;
    void Build(int l,int r,int num)
    {
        t[num].l=l;
        t[num].r=r;
        t[num].color=1;
        if(l==r)
            return;
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
    }
    void Getcolor(int l,int r,int num)//获得颜色种数
    {
        if(t[num].color!=-1)//如果区间内颜色为一种,就把该颜色的vis置为1,不用往下搜索了
        {
            vis[t[num].color]=1;
            return;
        }
        int mid=(t[num].l+t[num].r)/2;//后面写法和一般的询问一样
        if(r<=mid)
            Getcolor(l,r,num*2);
        else if(l>mid)
            Getcolor(l,r,num*2+1);
        else
        {
            Getcolor(l,mid,num*2);
            Getcolor(mid+1,r,num*2+1);
        }
    }
    void update(int l,int r,int num,int c)//更新区间
    {
        if(t[num].l==l&&t[num].r==r)//找到该区间,修改后返回
        {
            t[num].color=c;
            return;
        }
        if(t[num].color==c)//大区间和要修改的颜色一样则返回，不用往下修改了
            return;
        if(t[num].color!=-1)//lazy tag,如为同种颜色,更新子区间
        {
            t[num*2].color=t[num].color;
            t[num*2+1].color=t[num].color;
            t[num].color=-1;//将该区间标记为多种颜色
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            update(l,r,num*2,c);
        else if(l>mid)
            update(l,r,num*2+1,c);
        else
        {
            update(l,mid,num*2,c);
            update(mid+1,r,num*2+1,c);
        }
    }
    int main()
    {
        int i,j,x,y,c;
        scanf("%d%d%d",&L,&m,&n);
        char ch;
        Build(1,L,1);
        for(i=1;i<=n;i++)
        {
            getchar();
            scanf("%c",&ch);
            if(ch=='C')
            {
                scanf("%d%d%d",&x,&y,&c);
                if(x>y)//保证区间从小到大
                    swap(x,y);
                update(x,y,1,c);
            }
            else
            {
                scanf("%d%d",&x,&y);
                if(x>y)
                    swap(x,y);
                memset(vis,0,sizeof(vis));
                Getcolor(x,y,1);
                int ans=0;
                for(j=1;j<=m;j++)
                    if(vis[j])//找出区间内有几种颜色
                        ans++;
                printf("%d\n",ans);
            }
        }
        return 0;
    }