学步园

题目链接：  poj 2777 Count Color

题目大意：  给出一块长度为n的板，区间范围[1,n]，和m种染料

                    k次操作，C  a  b  c 把区间[a,b]涂为c色，P  a  b 查询区间[a,b]有多少种不同颜色

解题思路：  很明显的线段树的区间插入和区间查询，但是如何统计有多少不同的颜色呢？

                    如果每个结点数组来存储颜色的种类，空间复杂度很高，而且查询很慢

                    颜色最多只有30种，可以用位运算中的“按位或｜”

                    颜色也用二进制来处理，和存储：

                    第一种颜色的二进制表示1

                    第二种颜色的二进制表示10

                    第三种颜色的二进制表示100

                    第四种颜色的二进制表示1000

                    如同一个区间出现第一种和第三种颜色，按位或运算之后得到 101

                    统计结果有多少个1，就说明区间有多少不同的颜色

                    线段树每个结点存储区间颜色的种类，结点＝左子树｜右子树

                    更多关于线段树的解题报告可以看我博客 myzee.cn

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 110000
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1|1)
typedef struct{
    int left,right;
    int add,num;
}Node;
Node Tree[MAX<<2];
int Color[32]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824};
    //二进制表示第几种颜色，如8表示第四种颜色：1000
int Lowbit(int x)   //剔除x二进制中最后面一个1
{
    return x&(-x);
}

void Build(int t,int l,int r)  //以1为根结点，建立[l,r]的线段树
{
    Tree[t].left=l,Tree[t].right=r,Tree[t].add=0;  //***
    if(l==r)
    {
        Tree[t].num=1;
        return ;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
    Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num);
}

void Insert(int t,int l,int r,int m)  //向区间[l,r]涂颜色
{
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].add=m;
        Tree[t].num=m;
        return ;
    }
    if(Tree[t].add!=0)  //lazy标记
    {
        Tree[L(t)].num=Tree[t].add;
        Tree[R(t)].num=Tree[t].add;
        Tree[L(t)].add=Tree[t].add;
        Tree[R(t)].add=Tree[t].add;
        Tree[t].add=0;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        Insert(R(t),l,r,m);
    }
    else if(r<=mid)
    {
        Insert(L(t),l,r,m);
    }
    else
    {
        Insert(L(t),l,mid,m);
        Insert(R(t),mid+1,r,m);
    }
    Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num); //***
}

int Query(int t,int l,int r)
{
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        return Tree[t].num;
    }
    if(Tree[t].add!=0)  //区间插入的lazy思想
    {
        Tree[L(t)].num=Tree[t].add;
        Tree[R(t)].num=Tree[t].add;
        Tree[L(t)].add=Tree[t].add;
        Tree[R(t)].add=Tree[t].add;
        Tree[t].add=0;
    }
    int mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)
    {
        return Query(R(t),l,r);
    }
    else if(r<=mid)
    {
        return Query(L(t),l,r);
    }
    else
    {
        return Query(L(t),l,mid)|Query(R(t),mid+1,r);   //***是｜，不是＋!!!
    }
    Tree[t].num=(Tree[L(t)].num|Tree[R(t)].num);
}

int main()
{
    char ch;
    int n,col,q,i,k,a,b,c;
    int m;
    while(scanf("%d%d%d",&n,&col,&q)!=EOF)
    {
        memset(Tree,0,sizeof(Tree)); //初始化
        Build(1,1,n);                //建树
        for(i=0;i<q;i++)
        {
            getchar();
            scanf("%c",&ch);
            if(ch=='P')
            {
                scanf("%d%d",&a,&b);
                k=0;
                if(a>b)
                    m=Query(1,b,a);
                else
                    m=Query(1,a,b);
                while(m>0)    //计算查询后的结果的二进制表示右多少个1
                {
                    k++;
                    m-=Lowbit(m);
                }
                printf("%d\n",k);
            }
            else
            {
                scanf("%d%d%d",&a,&b,&c);
                if(a>b)
                    Insert(1,b,a,Color[c]);
                else
                    Insert(1,a,b,Color[c]);
            }
        }
    }
    return 0;
}

注：原创文章，转载请注明出处