昊昊喜欢运动

他N天内会参加M种运动(每种运动用一个[1,m]的整数表示)

现在有Q个操作，操作描述如下

• 昊昊把第l天到第r天的运动全部换成了x(x∈[1,m])
• 问昊昊第l天到第r天参加了多少种不同的运动

输入两个数N, M (1≤N≤105, 1≤M≤100);

输入N个数ai(ai∈[1,m])表示在第i天昊昊做了第ai类型的运动;

输入一个数Q(1≤Q≤105);

输入Q行 每行描述以下两种操作

• 形如M l r x，表示昊昊把第l天到第r天的运动全部换成了x(x∈[1,m])
• 形如Q l r，表示昊昊想知道他第l天到第r天参加了多少种不同的运动

对于所有的Q操作，每一行输出一个数 表示昊昊在第l天到第r天一共做了多少种活动

5 3 
1 2 3 2 3 
4 
Q 1 4 
Q 2 4 
M 5 5 2 
Q 1 5

3 
2 
3

 /******************************

 code by drizzle

 blog: www.cnblogs.com/hsd-/

 ^ ^    ^ ^

  O      O

 ******************************/

 //#include<bits/stdc++.h>

 #include<iostream>

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<bitset>

 //#define ll long long

 #define mod 1000000007

 #define PI acos(-1.0)

 using namespace std;

 struct node

 {

     int l,r;

     int add;

     bitset<> sum;

 } tree[];

 int n,m;

 int exm;

 int l1,r1,x;

 int q;

 char judge;

 void buildtree(int root,int left,int right)

 {

     tree[root].l=left;

     tree[root].r=right;

     tree[root].add=;

     if(left==right)

     {

         tree[root].sum.reset();

         scanf("%d",&exm);

         tree[root].sum[exm]=;

         return ;

     }

     int mid=(left+right)>>;

     buildtree(root<<,left,mid);

     buildtree(root<<|,mid+,right);

     tree[root].sum=tree[root<<].sum|tree[root<<|].sum;//按位或得到新的运动种类

 }

 void pushdown(int root)

 {

     if(tree[root].add==)

         return ;

     tree[root<<].sum.reset();

     tree[root<<|].sum.reset();

     tree[root<<].sum[tree[root].add]=;

     tree[root<<|].sum[tree[root].add]=;

     tree[root<<].add=tree[root].add;//注意延迟标记也要往下传

     tree[root<<|].add=tree[root].add;

     tree[root].add=;

 }

 void updata(int root,int left,int right,int c)

 {

     if(tree[root].l==left&&tree[root].r==right)

     {

         tree[root].sum.reset();//全部置零

         tree[root].add=c;

         tree[root].sum[c]=;//整个区间只有c运动

         return ;

     }

     pushdown(root);//lazy 延迟标记

     int mid=(tree[root].l+tree[root].r)>>;

     if(right<=mid)

         updata(root<<,left,right,c);

     else

     {

         if(left>mid)

             updata(root<<|,left,right,c);

         else

         {

             updata(root<<,left,mid,c);

             updata(root<<|,mid+,right,c);

         }

     }

     tree[root].sum=tree[root<<].sum|tree[root<<|].sum;

 }

 bitset<> query(int root,int left,int right)

 {

     if(tree[root].l==left&&tree[root].r==right)

     {

         return  tree[root].sum;

     }

     pushdown(root);

     int mid=(tree[root].l+tree[root].r)>>;

     if(right<=mid)

         return query(root<<,left,right);

     else

     {

         if(left>mid)

             return query(root<<|,left,right);

         else

             return query(root<<,left,mid)|query(root<<|,mid+,right);

     }

 }

 int main()

 {

     while(scanf("%d %d",&n,&m)!=EOF)

     {

         buildtree(,,n);

         scanf("%d",&q);

         getchar();

         for(int i=; i<=q; i++)

         {

             scanf("%c",&judge);

             if(judge=='Q')

             {

                 scanf("%d %d",&l1,&r1);

                 printf("%d\n",query(,l1,r1).count());

             }

             else

             {

                 scanf("%d %d %d",&l1,&r1,&x);

                 updata(,l1,r1,x);

             }

             getchar();//坑点

         }

     }

     return ;

 }