题解 2018寒假训练6(断网练习) D.染色种数
zhouwc
2018-02-25 09:34:50
问题 D: 染色种数
时间限制: 1 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
罗老师有n个点需要染色,一开始这些点染的颜色都是1, 接下来有两种操作:
C a b c: 表示将[a, b]区间的点染成c颜色
P a b: 表示询问[a, b]区间现在有多少种颜色
对于每个询问操作,你需要输出相应的答案。
输入
输入n, C, m,分别表示有n个点,颜色种类最多C种, m个操作
接下来m行,每行输入一种操作
输出
对于每个询问输出相应答案
样例输入
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
样例输出
2
1
提示
【数据规模和约定】
1<=n, m<=100000
1<= C <=30
1<= a, b <=n
1<= c <= C
```cpp
#include<stdio.h>
#include<cstring>
using namespace std;
int a[100005],b[35],n,m,c,k,x,y,z;
char s[3];
int main()
{
scanf("%d%d%d",&n,&c,&m);
for (int i=1;i<=n;i++)
a[i]=1;
for (int i=1;i<=m;i++)
{
scanf("%s",s);
if (s[0]=='C')
{
scanf("%d%d%d",&x,&y,&z);
for (int j=x;j<=y;j++)
a[j]=z;
}
else
{
scanf("%d%d",&x,&y);
k=0;
memset(b,0,sizeof(b));
for (int j=x;j<=y;j++)
{
b[a[j]]=1;
}
for (int j=1;j<=c;j++)
{
if (b[j]!=0) k=k+1;
}
printf("%d\n",k);
}
}
}
```