题目背景

阿宝上学了，今天老师拿来了一块很长的涂色板。

题目描述

色板长度为\(L\)，\(L\)是一个正整数，所以我们可以均匀地将它划分成\(L\)块\(1\)厘米长的小方格。并从左到右标记为\(1, 2, ... L\)。

现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：

  1. "\(C\) \(A\) \(B\) \(C\)" 指在\(A\)到 \(B\) 号方格中涂上颜色 \(C\)。
  2. "\(P\) \(A\) \(B\)"指老师的提问：\(A\)到 \(B\)号方格中有几种颜色。

学校的颜料盒中一共有 \(T\) 种颜料。为简便起见，我们把他们标记为 \(1, 2, ... T\). 开始时色板上原有的颜色就为\(1\)号色。 面对如此复杂的问题，阿宝向你求助，你能帮助他吗？

输入输出格式

输入格式：

第一行有\(3\)个整数 \(L (1 \leq L \leq 100000)\), \(T (1 \leq T \leq 30)\) 和 \(O (1 \leq O \leq 100000)\)。 在这里\(O\)表示事件数。
接下来 \(O\) 行, 每行以 "\(C\) \(A\) \(B\) \(C\)" 或 "\(P\) \(A\) \(B\)" 得形式表示所要做的事情(这里 \(A\), \(B\), \(C\) 为整数, 可能\(A\)> \(B\)，这样的话需要你交换\(A\)和\(B\))

输出格式：

对于老师的提问，做出相应的回答。每行一个整数。

输入输出样例

输入样例#1：

2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2

输出样例#1：

2
1

思路：正解貌似是基于二进制来建线段树，但是我不会……于是我就非常暴力的建了\(t\)棵线段树，因为\(t\)只有\(30\)嘛，所以建\(30\)棵线段树也不会爆，没棵线段树代表一个颜色，然后对于每一个\(C\)操作，就是修改要修改的那个颜色的对应线段树的对应修改区间为\(1\)，其余线段树的对应修改区间修改为\(0\)，然后查询就是把每棵线段树的区间颜色数加起来。但是代码可能因为常数优化的不太好等原因，不开\(O(2)\)会\(TLE\)一个点。

代码：

#include<cstdio>
#include<algorithm>
#define maxn 100007
#define ls rt<<1
#define rs rt<<1|1
#define re register
using namespace std;
int n,t,m,sum[31][maxn<<2],lazy[31][maxn<<2];
char s[2];
inline void pushup(int i, int rt) {
  sum[i][rt]=sum[i][ls]+sum[i][rs];
}
inline void pushdown(int i, int rt) {
  if(lazy[i][rt]==-1) {
    sum[i][ls]=sum[i][rs]=0;
    lazy[i][ls]=lazy[i][rs]=-1; 
  }
  else {
    lazy[i][ls]=lazy[i][rs]=lazy[i][rt];
    sum[i][ls]=sum[i][rs]=lazy[i][rt];
  }
  lazy[i][rt]=0;
}
void build(int rt, int l, int r) {
  if(l==r) {
    sum[1][rt]=1;
    return;
  }
  int mid=(l+r)>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(1,rt);
}
void modify(int i, int rt, int l, int r, int L, int R, int val) {
  if(L>r||R<l) return;
  if(L<=l&&r<=R) {
    sum[i][rt]=val;
    if(!val) lazy[i][rt]=-1;
    else lazy[i][rt]=val;
    return;
  }
  if(lazy[i][rt]) pushdown(i,rt);
  int mid=(l+r)>>1;
  if(L<=mid) modify(i,ls,l,mid,L,R,val);
  if(R>mid) modify(i,rs,mid+1,r,L,R,val);
  pushup(i,rt);
}
int csum(int i, int rt, int l, int r, int L, int R) {
  if(L>r||R<l) return 0;
  if(L<=l&&r<=R) return sum[i][rt];
  if(lazy[i][rt]) pushdown(i,rt);
  int mid=(l+r)>>1;
  return csum(i,ls,l,mid,L,R)+csum(i,rs,mid+1,r,L,R);
}
int main() {
  scanf("%d%d%d",&n,&t,&m);
  build(1,1,n);
  for(re int i=1,l,r,v;i<=m;++i) {
    scanf("%s%d%d",s,&l,&r);
    if(l>r) swap(l,r);
    if(s[0]=='C') {
      scanf("%d",&v);
      for(re int k=1;k<=t;++k) {
        if(k!=v) modify(k,1,1,n,l,r,0);
        else modify(k,1,1,n,l,r,1);
      }
    }
    else {
      int zrj=0;
      for(re int k=1;k<=t;++k) 
        if(csum(k,1,1,n,l,r)) zrj++;
      printf("%d\n",zrj);
    }
  }
  return 0;
}