#include <iostream> //poj 2777 Count Color 線段樹+位運算
using namespace std;
struct node
{
int l,r,color; //采用位運算代替用一個vis[]數組來表示哪些顔色存在或不存在，這樣既省空間也省時間
}tree[300000];
int c,count;
void build(int s,int t,int num)
{
tree[num].l=s;tree[num].r=t;
tree[num].color=1;
if(s!=t)
{
int mid=(s+t)/2;
build(s,mid,num*2);
build(mid+1,t,num*2+1);
}
}
int calculate(int p) //計算出p值所含的顔色種類數
{
int s=0;
while(p>0)
{
s++;
p-=(p&(-p));
}
return s;
}
void modify(int a,int b,int num)
{
//因為在插入一個區間時，當插入區間等于目前區間時，目前區間的顔色
//數目就變為了1，目前區間的孩子區間也全都變為1，是以不須一直更新到最底層
//等到重新插入另一個區間時再來更新孩子區間的顔色數,如果一直更新到最底層,則會TLE
if(calculate(tree[num].color)==1&&tree[num].l<tree[num].r) //tree[num].l<tree[num].r,如果是葉子節點，則無需更新左右子樹
{
tree[num*2].color=tree[num*2+1].color=tree[num].color; //更新孩子區間的顔色數,如果該區間的顔色數不是1的話，則它的孩子區間也必已更新了
}
if(tree[num].l==a&&tree[num].r==b) //隻有當插入區間等于目前區間時，才不用去更新它的孩子區間,每次插入時上面的if語句已經更新了
tree[num].color=c;
else
{
if(b<=tree[num*2].r)
modify(a,b,num*2);
else if(a>=tree[num*2+1].l)
modify(a,b,num*2+1);
else
{
int mid=(tree[num].l+tree[num].r)/2; //注意不是 mid=(a+b)/2;
modify(a,mid,num*2);
modify(mid+1,b,num*2+1);
}
tree[num].color=tree[num*2].color | tree[num*2+1].color;
}
}
void query(int a,int b,int num)
{
if(calculate(tree[num].color)==1&&tree[num].l<tree[num].r)
{
tree[num*2].color=tree[num*2+1].color=tree[num].color;
}
if(a==tree[num].l&&b==tree[num].r)
count=count | tree[num].color;
else
{
if(b<=tree[num*2].r)
query(a,b,num*2);
else if(a>=tree[num*2+1].l)
query(a,b,num*2+1);
else
{
int mid=(tree[num].l+tree[num].r)/2; //注意不是 mid=(a+b)/2;
query(a,mid,num*2);
query(mid+1,b,num*2+1);
}
}
}
int main()
{
int L,T,O,a,b;char ch;
cin>>L>>T>>O;
build(1,L,1);
while(O--)
{
cin>>ch;
if(ch=='C')
{
scanf("%d%d%d",&a,&b,&c);
if(a>b)swap(a,b);
c=1<<c-1; //相當于c=1<<(c-1)
modify(a,b,1);
}
else
{
count=0;
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
query(a,b,1);
printf("%d\n",calculate(count));
}
}
return 0;
}
//采用位運算可以大大節約時間
//顔色的表示方法。題目上有說明“T<=30”，顔色的種類不多(2<<T在int 範圍内)，是以使用二進制來存儲顔
//色的資訊,第n位上有 1 則表示是顔色n。具體說來，就是用1表示顔色1，10表示顔色2，100表示顔色3, 1001
//= 9表示 1 , 4 這2種顔色 ……依次類推，這樣表示有一種好處，要統計出 不重複 的顔色的種類，假設某
//線段上原來有顔色 2 ，現在在某部分塗上顔色 2 ，那麼對 2 和 2 進行 或 | 運算, 還是 10 , 如果再
//在某部分塗上顔色4 (1000)，與原來的 10 進行 或 | 運算，得到 1010 ，在這個二進制數找出有幾個1,
//就可以求出這條線段包含有幾種不重複的顔色。有兩個 1，說明有兩種顔色（ 2 和 4）。如何在二進制數找出
//有幾個 1 , 可以這樣統計 1 的個數：
//int calculate(int p)
//{
// int s=0;
// while(p>0)
// {
// s++;
// p-=(p&(-p)); //每次都把右邊起的第1個 1 變成 0
// }
// return s;
//}
//比如10100， 10100&(-10100)=100, 10100-100=10000
//10000&(-10000)=10000, 10000-10000=0 至此循環終止， s=2, 表示有兩個1
