Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

题意:“C”操作代表将[a,b]区间刷成颜色c
“p”操作询问区间[a,b]内颜色的数量
题解:
本题的突破口在这句「number of different colors T is very small. 」,题目给定范围是0-30,用二进制的话刚好在int范围内,既用一个30位的二进制数储存每个节点的颜色情况,有的为1,没有的为0,这种存储方式很像胜利大逃亡(续)中储存钥匙情况的模式,很经典的状态压缩方式。
每次只要处理一下PushUp的值就可以了,初始颜色为1,需要注意这句「A may be larger than B」,贡献了8次WA
//
// main.cpp
// 专题9-线段树
//
// Created by Edwin on 2019/3/2.
// Copyright © 2019 Edwin. All rights reserved.
//
//#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdio.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn 100000+10
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define SZ(V) (int)V.size()
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,0,n-1
#define delf int m = (r + l) / 2
using namespace std;
int lazy[maxn<<2];
int Hash[maxn<<2];//线段树,记录每个树的颜色情况,30种颜色用位运算记录
void init(){
mst(lazy,0);
mst(Hash,1);
}
void PushUp(int rt){
Hash[rt]=Hash[rt<<1]|Hash[rt<<1|1];
}
void PushDown(int rt){
if(lazy[rt]){
lazy[rt<<1]=lazy[rt];
lazy[rt<<1|1]=lazy[rt];
Hash[rt<<1] = lazy[rt];
Hash[rt<<1|1] = lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
if (l==r){
Hash[rt]=1;
return;
}
delf;
build(lson);
build(rson);
PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt){//区间更新
if(L > r || R < l )
return ;
if (L<=l&&r<=R){
Hash[rt]=1<<(c-1);
lazy[rt]=1<<(c-1);
return;
}
delf;
PushDown(rt);
if (L<=m) update(L,R,c,lson);
if (R>m) update(L,R,c,rson);
PushUp(rt);
}
ll query(int ql,int qr,int l,int r,int rt){
if(ql > qr) return 0;
if(ql > r || qr < l) return 0;
if(ql <= l && r <= qr){
return Hash[rt];
}
delf;
PushDown(rt);
return query(ql,qr,lson)|query(ql,qr,rson);
}
int countbits(ll value){
int count = 0;
while(value){
if(value & 1)
count++ ;
value >>= 1 ;
}
return count;
}
int main(){
int l,t,q;
scanf("%d %d %d",&l,&t,&q);
init();
build(1,l,1);
while(q--){
char str[2];
scanf("%s",str);
if(str[0]=='C'){
int ql,qr,c;
scanf("%d%d%d",&ql,&qr,&c);
if(ql > qr)
swap(ql,qr);
update(ql,qr,c,1,l,1);
}
else{
int ql,qr;
sc2(ql,qr);
if(ql > qr)
swap(ql,qr);
printf("%d\n",countbits(query(ql,qr,1,l,1)));
}
}
return 0;
}