题目描述
选择问题解决和程序设计作为可选课程,您需要解决各种问题。在这里,我们遇到了一个新问题。 有一块很长的板,长度为L厘米,L是正整数,因此我们可以将板均匀地分成L段,并且它们被标记为1,2,…L从左到右,每个长1厘米。现在,我们必须为电路板着色 - 一个只有一种颜色的段。我们可以在电路板上执行以下操作两个操作: 1.”C A B C”用颜色C将电路板从段A着色到B段。 “P A B” 输出在段 A 和段 B 之间绘制的不同颜色的数量(包括)。 在我们的日常生活中,我们很少有词来形容一种颜色(红色,绿色,蓝色,黄色......),所以你可能会认为不同颜色T的总数非常少。为简单起见,我们将颜色的名称表示为颜色1,颜色2,…颜色 T。一开始,板子被涂成1色。现在剩下的问题留给你了。
输入
输入的第一行包含 L (1 <= L <= 100000)、T (1 <= T <= 30) 和 O (1 <= O <= 100000)。此处 O 表示操作数。在O行之后,每个都包含”C A B C”或”P A B”(此处A,B,C是整数,A可能大于B)作为先前定义的操作。
输出
输出结果按顺序输出运算,每行包含一个数字。
样例
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
2
1
二进制
利用col属性储存颜色,当col在二进制下是 0010时代表有第二种颜色,细节操作在代码中。
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define int long long
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double, double> PDD;
const int N = 100010;
int n,ans;
int l,t,op;
struct node{
int l,r;
int col,lazy;
}tr[N*4];
void pushup(int u)
{
tr[u].col=tr[u<<1].col|tr[u<<1|1].col;
}
void pushdown(int u)
{
if(tr[u].lazy)
{
tr[u<<1].col=tr[u<<1|1].col=tr[u].col;
tr[u<<1].lazy=tr[u<<1|1].lazy=tr[u].lazy;
tr[u].lazy=0;
}
}
void build(int u,int l,int r)
{
tr[u]={l,r,1,0};
if(l!=r)
{
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int x)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
tr[u].col=x;
tr[u].lazy=1;
return ;
}
else
{
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,x);
if(r>mid) modify(u<<1|1,l,r,x);
pushup(u);
}
}
void query(int u,int l,int r)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
ans|=tr[u].col;
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) query(u<<1,l,r);
if(r>mid) query(u<<1|1,l,r);
pushup(u);
}
void slove()
{
build(1,1,l);
while(n--)
{
int a,b,c;
char op[2];
scanf("%s",op);
if(op[0]=='C')
{
scanf("%lld%lld%lld",&a,&b,&c);
if(a>b) swap(a,b);
modify(1,a,b,(1<<(c-1)));
// cout<<"-----"<<endl;
}
else
{
scanf("%lld%lld",&a,&b);
if(a>b) swap(a,b);
ans=0;
query(1,a,b);
int res=0;
for(int i=0;i<=30;i++) if((ans>>i)&1) res++;
cout<<res<<endl;
}
}
}
signed main()
{
while(scanf("%lld%lld%lld",&l,&t,&n)!=EOF)
{
slove();
}
}