GDUT-寒假专题训练5--Count Color

题目：

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample

Inputcopy	Outputcopy
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2	2 1

题意：有一个长为L的区间，现在有T种颜色，有O次操作，若输入是C A B D，就给A到B的区间染上颜色D，若输入是P A B，就查询区间A到B有多少种颜色，（A不一定比B大）

题解：考虑到颜色种类最大只有30，那么我们就可以用二分数组来储存颜色的个数，在线段树中储存一段十进制的数，他们转为二进制后第N位就表示第N种颜色，线段树向上合并的时候用或运算即可

代码：

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int b[400010],lazy[400010],ans,cc;

inline void push(int xb)
{
 b[xb]=b[xb*2]|b[xb*2+1];//或运算向上储存
}

inline void down(int l,int r,int xb)//向下储存这个十进制数
{
 if (lazy[xb])
 {
  lazy[xb*2+1]=lazy[xb];
  lazy[xb*2]=lazy[xb];
  b[xb*2]=lazy[xb];
  b[xb*2+1]=lazy[xb];
  lazy[xb]=0;
 }
} 

inline void  build(int l,int r,int xb)
{
 lazy[xb]=0;
 if (l==r)
 {
  b[xb]=1;return;//l=r时最末端只可能有一种颜色
 }
 build(l,(l+r)/2,xb*2);
 build((l+r)/2+1,r,xb*2+1);
 push(xb);
}

inline void qujian(int ll,int rr,int val,int l,int r,int xb)
{
 if (ll<=l&&rr>=r)
 {
  b[xb]=val;//!
  lazy[xb]=val;//!
  return;
 }
 int m=(l+r)/2;
 down(l,r,xb);
 if (ll<=m)qujian(ll,rr,val,l,m,xb*2);
 if  (rr>m)qujian(ll,rr,val,m+1,r,xb*2+1);
 push(xb);//处理完毕后要向上更新
}

inline void  query(int ll,int rr,int l,int r,int xb){
 if (ll<=l&&rr>=r){ans=ans|b[xb];return;}//答案运算时也是要用或运算
 int m=(l+r)/2;
 down(l,r,xb);
 int ans=0;
 if (rr>m) query(ll,rr,m+1,r,xb*2+1);
 if (ll<=m) query(ll,rr,l,m,xb*2);
}

inline int check(int ans)//转回二进制并算出1的个数
{
 int c=cc;int d=0;
 while(ans>0)
 {
  if (ans>=c)
   {ans=ans-c;
   d++;}
  c=c/2;
  
 }
 return d;
}

int main()
{
 int n,m,ll,rr,val,l,t,o,c[51];char p;
 cin >> l >> t >> o;
 cc=1;
 for (int i=1;i<=t;i++) {c[i]=cc;cc=cc*2;}//想要二进制的位数变高乘二即可
    build(1,l,1);
 for (int i=1;i<=o;i++)
 {
  cin >> p;
  if (p=='P')
  {
   ans=0;
   cin >> ll >> rr;
   if (ll>rr) swap(ll,rr);//l不一定比r大
   query(ll,rr,1,l,1);
   cout << check(ans) << endl;
  }
  if (p=='C')
  {
   cin >> ll >> rr >> val;
   if (ll>rr) swap(ll,rr);//l不一定比r大
   qujian(ll,rr,c[val],1,l,1);//c[val]中储存的数是第i个元素下的二进制的那个1转化成10进制下的值
  }
 }
}