英雄哪里出來

/*
題意：
    給定一個長度為N(N <= 100000)的數(shù)列Si，緊接著Q(Q <= 100000)條操作，操作
形式有兩種：
1. "C A B C" 將A到B的數(shù)都染成C這種顏色。 
2. "P A B" 輸出A和B之間不同顏色的數(shù)目。


解法：
線段樹（染色問題）

思路：
    一看到數(shù)據(jù)量就可以首先確定是線段樹了，經(jīng)典的區(qū)間染色問題，涉及到區(qū)間的
更新和詢問，和pku 3468 類似，巧妙運用lazy思想。就是每次更新區(qū)間段的時候延遲
更新，只是在完全覆蓋的區(qū)間打上一個lazy標(biāo)記。這題的詢問是求區(qū)間段中不同顏色的
數(shù)量，因為顏色數(shù)不多只有30種，可以巧妙運用二進制位運算，用一個int就可以表示
當(dāng)前區(qū)間段的顏色情況。比如1001表示有兩種顏色，如果左子樹的當(dāng)前顏色情況是101
，而右子樹的顏色情況是011，那么父親的顏色情況就是兩者的位或，這樣就可以避免
掉重復(fù)的情況。
    再來談?wù)刲azy思想。做了這么多的線段樹，應(yīng)該總結(jié)一下，lazy是一個很經(jīng)典的思
想。所謂lazy，就是懶惰，每次不想做太多，只要插入的區(qū)間完全覆蓋了當(dāng)前結(jié)點所管
理的區(qū)間就不再往下做了，在當(dāng)前結(jié)點上打上一個lazy標(biāo)記，然后直接返回。下次如果
遇到當(dāng)前結(jié)點有l(wèi)azy標(biāo)記的話，直接傳遞給兩個兒子，自己的標(biāo)記清空。這樣做肯定是
正確的。我們以染色為例，可以這樣想，如果當(dāng)前結(jié)點和它的子孫都有l(wèi)azy標(biāo)記的話，
必定是子孫的先標(biāo)記，因為如果是自己先標(biāo)記，那么在訪問子孫的時候，必定會將自己
的標(biāo)記下傳給兒子，而自己的標(biāo)記必定會清空，那么lazy標(biāo)記也就不存在了。所以可以
肯定，當(dāng)前的lazy標(biāo)記必定覆蓋了子孫的，所以直接下傳即可，不需要做任何判斷。當(dāng)
然，這是染色問題，是直接賦值的，如果像pku 3468那樣，每次是區(qū)間加和，則傳遞標(biāo)
記的時候不能簡單的賦值，必須累加，這是顯而易見的。
*/
/*
lazy思想
    染色模型
        適合顏色數(shù)目較少(64以內(nèi))的區(qū)間染色問題。
        具體操作：
            1、對某個連續(xù)區(qū)間進行染色。
            2、詢問某個連續(xù)區(qū)間的顏色情況（種類、數(shù)目等等）。
        適用題型：
            poj 2777 Count Color
            hdu 5023 A Corrupt Mayor's Performance Art
        結(jié)點存儲
            顏色值的位或colorBit：每個顏色用2的冪來表示，顏色值表示分別為1、2、4、8，該區(qū)間有哪些顏色就可以用他們的或來表示
            延遲標(biāo)記lazy：該段區(qū)間完全被染色成了lazy這種顏色，這里的lazy要么是2的冪，要么是0

        接口說明
            giveLazyToSon      傳遞延遲標(biāo)記給兩個子結(jié)點（調(diào)用子結(jié)點的updateByValue，并且lazy重置）
            updateByValue      通過某個顏色值更新當(dāng)前結(jié)點信息（更新colorBit、lazy）
            updateFromSon      通過兩個子結(jié)點更新當(dāng)前結(jié)點信息（更新colorBit）
            mergeQuery         詢問時用于對分割后的子結(jié)點進行合并用，不同情況實現(xiàn)不同

        調(diào)用說明
            建樹：              調(diào)用靜態(tài)函數(shù)   treeNode::segtree_build(1, 1, n);
            插入([x, y], val)： 調(diào)用靜態(tài)函數(shù)   treeNode::segtree_insert(1, 1, n, x, y, val);
            詢問([x, y]):       調(diào)用靜態(tài)函數(shù)   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();

    // 詢問的時候?qū)⒔Y(jié)點合并后計入答案
    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);
    // 區(qū)間詢問[x, y]上的信息
    static void segtree_query(int p, int l, int r, int x, int y, treeNode& ans);
};

/* 全局變量 
    nodes[MAXN*2] 存儲所有靜態(tài)線段樹結(jié)點(動態(tài)開內(nèi)存太費時間)
    totalNodes    存儲結(jié)點數(shù)目
*/
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) {
    // 創(chuàng)建線段樹結(jié)點的時候只需要知道該線段樹結(jié)點管轄區(qū)間的長度，區(qū)間端點不用存，可以在遞歸的時候作為函數(shù)傳參
    nodes[p].reset(p, r-l+1);
      if (l < r) {
            int mid = (l + r) >> 1;
            // 遞歸創(chuàng)建左右兒子結(jié)點
        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
*/