洛谷P1558 色板游戏

题目背景

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

题目描述

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

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

"(C) (A) (B) (C)" 指在(A)到 (B) 号方格中涂上颜色 (C)。
"(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：

输出样例#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
",zrj);
    }
  }
  return 0;
}