英雄哪里出来

/*
题意：
    给定一个长度为N(N <= 100000)的数列Si，紧接着Q(Q <= 100000)条操作，操作
形式有两种：
1. "C A B C" 将A到B的数都染成C这种颜色。 
2. "P A B" 输出A和B之间不同颜色的数目。


解法：
线段树（染色问题）

思路：
    一看到数据量就可以首先确定是线段树了，经典的区间染色问题，涉及到区间的
更新和询问，和pku 3468 类似，巧妙运用lazy思想。就是每次更新区间段的时候延迟
更新，只是在完全覆盖的区间打上一个lazy标记。这题的询问是求区间段中不同颜色的
数量，因为颜色数不多只有30种，可以巧妙运用二进制位运算，用一个int就可以表示
当前区间段的颜色情况。比如1001表示有两种颜色，如果左子树的当前颜色情况是101
，而右子树的颜色情况是011，那么父亲的颜色情况就是两者的位或，这样就可以避免
掉重复的情况。
    再来谈谈lazy思想。做了这么多的线段树，应该总结一下，lazy是一个很经典的思
想。所谓lazy，就是懒惰，每次不想做太多，只要插入的区间完全覆盖了当前结点所管
理的区间就不再往下做了，在当前结点上打上一个lazy标记，然后直接返回。下次如果
遇到当前结点有lazy标记的话，直接传递给两个儿子，自己的标记清空。这样做肯定是
正确的。我们以染色为例，可以这样想，如果当前结点和它的子孙都有lazy标记的话，
必定是子孙的先标记，因为如果是自己先标记，那么在访问子孙的时候，必定会将自己
的标记下传给儿子，而自己的标记必定会清空，那么lazy标记也就不存在了。所以可以
肯定，当前的lazy标记必定覆盖了子孙的，所以直接下传即可，不需要做任何判断。当
然，这是染色问题，是直接赋值的，如果像pku 3468那样，每次是区间加和，则传递标
记的时候不能简单的赋值，必须累加，这是显而易见的。
*/
/*
lazy思想
    染色模型
        适合颜色数目较少(64以内)的区间染色问题。
        具体操作：
            1、对某个连续区间进行染色。
            2、询问某个连续区间的颜色情况（种类、数目等等）。
        适用题型：
            poj 2777 Count Color
            hdu 5023 A Corrupt Mayor's Performance Art
        结点存储
            颜色值的位或colorBit：每个颜色用2的幂来表示，颜色值表示分别为1、2、4、8，该区间有哪些颜色就可以用他们的或来表示
            延迟标记lazy：该段区间完全被染色成了lazy这种颜色，这里的lazy要么是2的幂，要么是0

        接口说明
            giveLazyToSon      传递延迟标记给两个子结点（调用子结点的updateByValue，并且lazy重置）
            updateByValue      通过某个颜色值更新当前结点信息（更新colorBit、lazy）
            updateFromSon      通过两个子结点更新当前结点信息（更新colorBit）
            mergeQuery         询问时用于对分割后的子结点进行合并用，不同情况实现不同

        调用说明
            建树：              调用静态函数   treeNode::segtree_build(1, 1, n);
            插入([x, y], val)： 调用静态函数   treeNode::segtree_insert(1, 1, n, x, y, val);
            询问([x, y]):       调用静态函数   treeNode::segtree_query(1, 1, n, x, y, ans);

*/ 
#include <iostream>

using namespace std;

#define MAXN 131072
typedef int ValueType;


// 返回[l, r]和[x, y]两条线段是否相交
bool is_intersect(int l, int r, int x, int y) {
      return !(r < x || l > y);
}
// 返回[x, y]是否完全包含[l, r]
bool is_contain(int l, int r, int x, int y) {
      return x <= l && r <= y;
}

struct treeNode {
    ValueType lazy;
    ValueType colorBit;
      int pid;
      int len;

    treeNode() {
        reset(-1, 0);
    }
      void reset(int p, int _len) {
        pid = p;
        colorBit = 0;
        lazy = 0;
        len = _len;
    }
    int lson() { return pid << 1; }
    int rson() { return pid<<1|1; }

    void updateByValue(ValueType _val);
    void giveLazyToSon();
    void updateFromSon();

    // 询问的时候将结点合并后计入答案
    void mergeQuery(int p);

    // 建树 
    static void segtree_build(int p, int l, int r);
    // 插入线段[x, y]到[l, r]
    static void segtree_insert(int p, int l, int r, int x, int y, ValueType val);
    // 区间询问[x, y]上的信息
    static void segtree_query(int p, int l, int r, int x, int y, treeNode& ans);
};

/* 全局变量 
    nodes[MAXN*2] 存储所有静态线段树结点(动态开内存太费时间)
    totalNodes    存储结点数目
*/
treeNode nodes[MAXN*2];

void treeNode::updateByValue(ValueType _val) {
    lazy = _val;
    colorBit = _val;
}

void treeNode::giveLazyToSon() {
      if(lazy) {
        nodes[ lson() ].updateByValue(lazy);
        nodes[ rson() ].updateByValue(lazy);    
        lazy = 0;        
    }
}

void treeNode::updateFromSon() {
    colorBit = nodes[ lson() ].colorBit | nodes[ rson() ].colorBit;
}

void treeNode::mergeQuery(int p) {
    colorBit |= nodes[p].colorBit;
}

void treeNode::segtree_build(int p, int l, int r) {
    // 创建线段树结点的时候只需要知道该线段树结点管辖区间的长度，区间端点不用存，可以在递归的时候作为函数传参
    nodes[p].reset(p, r-l+1);
      if (l < r) {
            int mid = (l + r) >> 1;
            // 递归创建左右儿子结点
        treeNode::segtree_build(p<<1, l, mid);
        treeNode::segtree_build(p<<1|1, mid+1, r);
        nodes[p].updateFromSon();
    }
}

void treeNode::segtree_insert(int p, int l, int r, int x, int y, ValueType val) {
      if( !is_intersect(l, r, x, y) ) {
            return ;
      }
      if( is_contain(l, r, x, y) ) {
        nodes[p].updateByValue(val);
            return ;
    } 
    nodes[p].giveLazyToSon();
      int mid = (l + r) >> 1; 
    treeNode::segtree_insert(p<<1, l, mid, x, y, val);
    treeNode::segtree_insert(p<<1|1, mid+1, r, x, y, val);
    nodes[p].updateFromSon();
}

void treeNode::segtree_query(int p, int l, int r, int x, int y, treeNode& ans) {
      if( !is_intersect(l, r, x, y) ) {
            return ;
      }
      if( is_contain(l, r, x, y) ) {
            ans.mergeQuery(p);
            return;
    }
    nodes[p].giveLazyToSon();
      int mid = (l + r) >> 1; 
    treeNode::segtree_query(p<<1, l, mid, x, y, ans);
    treeNode::segtree_query(p<<1|1, mid+1, r, x, y, ans);
    nodes[p].updateFromSon();
} 

int n, t, o;

int main() {
    int i;
    while( scanf("%d %d %d", &n, &t, &o) != EOF ) {
            treeNode::segtree_build(1, 1, n);
            for(i = 1; i <= n; i++) {
            treeNode::segtree_insert(1, 1, n, i, i, 1<<0);
            }
            while(o--) {
                  char str[10];
                  int x, y, z;

                  scanf("%s", str);
                  if(str[0] == 'C') {
                           scanf("%d %d %d", &x, &y, &z);
                           if(x > y) swap(x, y);
                           treeNode::segtree_insert(1, 1, n, x, y, 1<<(z-1) );
                  }else {
                           scanf("%d %d", &x, &y);
                           if(x > y) swap(x, y);
                 treeNode ans;
                 treeNode::segtree_query(1, 1, n, x, y, ans);
                 z = 0;
                          for(i = 0; i < t; i++) {
                                if( (1<<i) & ans.colorBit ) {
                        z ++;
                    }
                }
                printf("%d\n", z);
            }
        }
    }
    return 0;
}

/*
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
*/