题解 P1558 【色板游戏】
这题看上去好吓人啊,但第二眼看就可以发现t<=30,那么我们就可以状态压缩一下,如果一个数二进制的第i位为1,则这个数代表的区间里有第i个颜色的格子。 状压完毕。 之后我们再来看怎么套到线段树上,无非就是确定上推和下推规则,先看上推,我们可以直接按位于一下(因为只要求左右区间一个有这种颜色),再来下推,由于颜色可以覆盖,那么直接把原来的值给覆盖掉,lazy标记也是如此。 上代码:
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll sum[400001],n,t,c,i,ad[400001];
inline void pushup(ll rt){
sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}
inline void build(ll rt,ll l,ll r){
if (l==r){
sum[rt]=1<<1;
return;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
pushup(rt);
}
inline void pushdown(ll rt,ll l,ll r){
if (ad[rt]){
sum[rt<<1]=(1<<ad[rt]);
sum[rt<<1|1]=(1<<ad[rt]);
ad[rt<<1]=ad[rt];
ad[rt<<1|1]=ad[rt];
ad[rt]=0;
}
}
inline void update(ll rt,ll l,ll r,ll x,ll y,ll k){
if (l>y||x>r) return;
if (x<=l&&r<=y){
sum[rt]=(1<<k);
ad[rt]=k;
return;
}
pushdown(rt,l,r);
ll m=(l+r)>>1;
if (m>=x) update(rt<<1,l,m,x,y,k);
if (m<y) update(rt<<1|1,m+1,r,x,y,k);
pushup(rt);
}
inline int query(ll rt,ll l,ll r,ll x,ll y){
if (l>y||x>r) return 0;
if (x<=l&&r<=y) return sum[rt];
pushdown(rt,l,r);
ll m=(l+r)>>1,ans=0;
if (m>=x) ans|=query(rt<<1,l,m,x,y);
if (m<y) ans|=query(rt<<1|1,m+1,r,x,y);
return ans;
}
int main(){
char u; ll x,y,k;
scanf("%lld%lld%lld",&n,&c,&t);
build(1,1,n);
while (t--){
cin>>u;
if(u=='C'){
scanf("%lld%lld%lld",&x,&y,&k);
if (x>y) swap(x,y);
update(1,1,n,x,y,k);
}
else{
scanf("%lld%lld",&x,&y);
if (x>y) swap(x,y);
ll p=query(1,1,n,x,y),ans=0;
for (i=1; i<=c; i++) if (p&(1<<i)) ans++;
printf("%lld\n",ans);
}
}
return 0;
}