POJ 2777 Count Color 解题报告

一、问题描述

Description

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

二、解答思想

使用线段树进行求解。创建一个（1，L）的线段树。线段树的结构和定义如下：

struct Node

{

       int ld,rd;         //左右边界

       int left,right;    //左右孩子下标

       int color;        //保存这个区间的颜色数目

};

Node Tree[700001];//线段树

对于区间的颜色数用一个32位整数保存，该整数的2进制位每一位表示是否包含该颜色，对两个整数的或运算可以求这两个集合的并。

三、代码

参考http://www.cppblog.com/rakerichard/archive/2010/02/18/108011.html

 

#include<algorithm>
using namespace std;
struct Node
{
    int ld,rd;        //左右边界
    int left,right;    //左右孩子下标
    int color;        //保存这个区间的颜色数目
};
int len=0;    //长度
int L;        //墙的最大长度        
int T;        //总的颜色数
int O;        //输入行数
Node Tree[700001];//线段树
//交换两元素值
void Swap(int &a,int &b)
{
    int t=a;a=b;b=t;
}
//获取c代表的颜色数
int Colors(int c)
{
    int cn=0;
    for(int i=1;i<=T;++i)
    {
        if(c&(1<<i))
            cn++;
    }
    return cn;
}
//构造一棵线段树
void Build(int a ,int b)
{
    int mid=(a+b)>>1;
    int now;
    len++;
    now=len;
    Tree[now].ld=a;
    Tree[now].rd=b;
    Tree[now].color=2;//为啥子等于2? 2的1次方
    if(a<b)
    {
        Tree[now].left=len+1;
        Build(a,mid);
        Tree[now].right=len+1;
        Build(mid+1,b);
    }
}
//播放入一段线段
void Insert(int x,int y,int c ,int node)
{
    int a=Tree[node].ld;
    int b=Tree[node].rd;
    int t=(a+b)>>1;
    if(x<=a && b<=y)
        Tree[node].color=(1<<c);
    else
    {
        //因为在插入一个区间时，当插入区间大于当前区间时，当前区间的颜色
        //数目就变为了1，当前区间的孩子区间也都变为1，所以不须更新到最底层
        //到重新插入另一个区间时再更新孩子区间的颜色数
        if(Colors(Tree[node].color)<=1)
        {
            Tree[Tree[node].left].color=Tree[Tree[node].right].color=Tree[node].color;
        }
        if(t>=x)
            Insert(x,y,c,Tree[node].left);
        if(t+1<=y)
            Insert(x,y,c,Tree[node].right);
        Tree[node].color=Tree[ Tree[node].left ].color | Tree[ Tree[node].right ].color;
    }
}
//获取区间的颜色数目
int GetColor(int x,int y,int node)
{
    int lc=0;//左边的颜色
    int rc=0;//右边的颜色
    int a=Tree[node].ld;
    int b=Tree[node].rd;
    int t=(a+b)>>1;
    if(Colors(Tree[node].color)<=1)
        return Tree[node].color;
    if(x<=a && b<=y)
        return Tree[node].color;
    if(t>=x)
        lc=GetColor(x,y,Tree[node].left);
    if(t+1<=y)
        rc=GetColor(x,y,Tree[node].right);
    return lc | rc;

}
int main()
{
    scanf("%d%d%d",&L,&T,&O);
    len=0;
    Build(1,L);
    char ch[5] ;
    int A,B,C;
    for(int i=0;i<O;++i)
    {    
        scanf("%s",&ch);
        if(ch[0]=='C')
        {
            scanf("%d%d%d",&A,&B,&C);
            if(A>B)
                Swap(A,B);
            Insert(A,B,C,1);
        }
        else
        {
            if(ch[0]=='P')
            {
                scanf("%d%d",&A,&B);
                if(A>B)
                    Swap(A,B);
                int cc=GetColor(A,B,1);
                printf("%d\n",Colors(cc));
            }
        }
    }
    return 0;
}