POJ - 2777——Count Color（懒标记线段树二进制）-蒲公英云

Count Color

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 53639		Accepted: 16153

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:

“C A B C” Color the board from segment A to segment B with color C.
“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

Sample Output

2
1
题目链接：
http://poj.org/problem?id=2777
题目大意：
给L长度的木板涂色，一开始木板颜色相同，有T种颜色可用，O（不是零是 ou ）次操作。每次操作有两种情况，一种是改变木板的颜色也就是给木板的某个区间涂色，另一种是询问给定区间的颜色种类数量。
题目分析：
这题比较明显是使用线段树解决问题，但是有一个问题是：超时。那么如何解决这个问题呢，这时候就引进了一个很优秀的操作————懒标记。
懒标记是什么呢？“懒”的意思很明显了，就是说在不涉及某个节点的情况下，选择性的变懒，不去改变。举个例子：
如果改变区间的颜色，那么我们可以不去找到区间内每个叶子然后改变每个叶子的颜色，而是找到在这个区间内的另外的区间（可能是一个区间，也可能是很多个区间，也有可能包括了一个区间和n个叶子，也有可能只有叶子），把找到的区间改变颜色，并把区间懒标记。
懒标记后，如果再次查询到该节点，那么需要做下推操作，即把该节点的颜色，下推给子节点，改变子节点的颜色，并把该节点懒标记清空。
对于颜色的存储，这题还是需要注意的。我们很容易想到存储每个节点区间的颜色种类数，但是这样存储问题就来了，怎么确定子节点中颜色是否相同。所以有引进一个操作，二进制表示法。
我们可以看到颜色的种类不超过30种，所以可以用一位二进制表示一种颜色，即颜色一为（1），颜色二为（10），颜色三为（100），颜色四为（1000），依次类推。
那么我们存储父节点颜色怎么存储呢？      或操作（|）。
tree[k].color=tree[k<<1].color|tree[k<<1|1].color;
解释一下：或操作，如果颜色相同，那么结果仍保存该颜色；如果子节点一个有该颜色，另一个没有该颜色，操作结果仍然有该颜色；如果两个子节点都没有该颜色，那么结果也没有该颜色。
最后得到的结果只需要判断在二进制下有几个1就可以了。
还要注意一个坑就是 A和B大小不确定。
AC代码如下：
#include<stdio.h>
const int MAX=1e6+5;
struct a{
    int left,right;
    int  lazy,ans;
}tree[MAX<<2];
void init(int length)  //懒标记初始化 
{
    for(int i=1;i<=length;i++)
    {
        tree[i].lazy=0;
    }
}
void btree(int k,int l,int r)   //建树操作 
{
    tree[k].left=l;tree[k].right=r;
    if(l==r)
    {
        tree[k].ans=1;return ;
    }
    int mid=(l+r)>>1;
    btree(k<<1,l,mid);
    btree(k<<1|1,mid+1,r);
    tree[k].ans=(tree[k<<1].ans|tree[k<<1|1].ans);
}
void push_down(int k)    //下推 
{
    if(tree[k].left==tree[k].right) return ;
    tree[k<<1].lazy=tree[k].lazy;
    tree[k<<1|1].lazy=tree[k].lazy;
    tree[k<<1].ans=1<<(tree[k].lazy-1);
    tree[k<<1|1].ans=1<<(tree[k].lazy-1);
    tree[k].lazy=0;
}
void datetree(int k,int l,int r,int co)  //涂色 
{
    if(tree[k].left>=l&&tree[k].right<=r)
    {
        tree[k].ans=1<<(co-1);
        tree[k].lazy=co;
        return ;
    }
    if(tree[k].lazy) push_down(k);
    int mid=(tree[k].left+tree[k].right)>>1;
    if(mid<l)
    {
        datetree(k<<1|1,l,r,co);
    }
    else if(mid>=r)
    {
        datetree(k<<1,l,r,co);
    }
    else 
    {
        datetree(k<<1,l,r,co);
        datetree(k<<1|1,l,r,co);
    }
    tree[k].ans=(tree[k<<1].ans|tree[k<<1|1].ans);
}
int ans;
void query(int k,int l,int r)    //询问 
{
    if(tree[k].left>=l&&tree[k].right<=r)
    {
        ans=(ans|tree[k].ans);
        return ;
    }
    if(tree[k].lazy) push_down(k); 
    int mid=(tree[k].left+tree[k].right)>>1;
    if(mid<l)
    {
        query(k<<1|1,l,r);
    }
    else if(mid>=r)
    {
        query(k<<1,l,r);
    }
    else 
    {
        query(k<<1,l,r);
        query(k<<1|1,l,r);
    }
}
int main()
{
    int L,color,q;
    char n[10];
    scanf("%d%d%d",&L,&color,&q);
    init(L);
    btree(1,1,L);
    while(q--)
    {
        scanf("%s",n);
        if(n[0]=='C')
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a>b){
                int t=a;a=b;b=t;
            }
            datetree(1,a,b,c);
        }
        else
        {
            int a,b;
            ans=0;
            int cnt=0;
            scanf("%d%d",&a,&b);
            if(a>b){
                int t=a;a=b;b=t;
            }
            query(1,a,b);
            while(ans)
            {
                if(ans%2) cnt++;
                ans/=2;
            }
            printf("%d\n",cnt);
        }
    }
    return 0;
}