英雄哪里出來

/*
題意：
    給定一個長度為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
*/