$30$ 棵线段树
我们对于每一种颜色 $i$ 都开一棵线段树 $t[i]$ 维护区间是否染上了该颜色。
判断是否染上了该颜色只需要判断该区间内是否有 $1$。
维护区间最大值或者 bool || 运算即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5,T=30;
struct seg{
struct node{
int l,r;
bool value;
int tag;
}t[4*N+1];
void up(int p){
t[p].value = t[p<<1].value||t[p<<1|1].value;
}
void down(int p){
if(t[p].tag!=-1){
t[p<<1].value=t[p].tag;
t[p<<1].tag=t[p].tag;
t[p<<1|1].value=t[p].tag;
t[p<<1|1].tag=t[p].tag;
t[p].tag=-1;
}
}
void set(int p,int l,int r,bool k){
if(l<=t[p].l&&t[p].r<=r){
t[p].value=k;
t[p].tag=k;
return;
}
down(p);
if(l<=t[p<<1].r)set(p<<1,l,r,k);
if(t[p<<1|1].l<=r)set(p<<1|1,l,r,k);
up(p);
}
bool query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r)return t[p].value;
down(p);
if(l<=t[p<<1].r&&query(p<<1,l,r))return true;
if(t[p<<1|1].l<=r&&query(p<<1|1,l,r))return true;
return false;
}
void build(int p,int l,int r){
t[p]={l,r,false,-1};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
}t[31];
int n;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int q;
scanf("%d %*d %d",&n,&q);
for(int i=1;i<=30;i++)t[i].build(1,1,n);
t[1].set(1,1,n,true);
while(q--){
int a,b,c;
char ch;
cin>>ch>>a>>b;
if(a>b)swap(a,b);
switch(ch){
case 'C':
scanf("%d",&c);
for(int i=1;i<=30;i++){
t[i].set(1,a,b,i==c);
}
break;
case 'P':
int ans=0;
for(int i=1;i<=30;i++){
ans+=t[i].query(1,a,b);
}printf("%d\n",ans);
break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
但是这样很容易发现，会 $\text{MLE}$。因为：
\[30\times 4\times 10^5\times (4+4+1+4)\text{Byte}=156,000,000\text{Byte}\approx 149\text{MB}>128\text{MB}\]于是我们想办法卡空间。
不难发现线段树的结构体 node 中的子元素 $l,r$ 其实是可有可无的。因为 $l,r$ 完全可以在使用时算出来，也就是一种时间换空间。
这样我们去除 $l,r$ 后，单个 node 的大小便为 $(1+4)\text{Byte}=5\text{Byte}$，总大小便缩减到了约 $58\text{MB}$。
不过需要注意的是，这样会增大递归开销（详见代码），因此最终内存使用量会增多至约 $90\text{MB}$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5,T=30;
struct seg{
struct node{
bool value;
int tag;
}t[4*N+1];
void up(int p){
t[p].value = t[p<<1].value||t[p<<1|1].value;
}
void down(int p){
if(t[p].tag!=-1){
t[p<<1].value=t[p].tag;
t[p<<1].tag=t[p].tag;
t[p<<1|1].value=t[p].tag;
t[p<<1|1].tag=t[p].tag;
t[p].tag=-1;
}
}
void set(int p,int pl,int pr,int l,int r,bool k){
if(l<=pl&&pr<=r){
t[p].value=k;
t[p].tag=k;
return;
}
down(p);
int mid=pl+pr>>1;
if(l<=mid)set(p<<1,pl,mid,l,r,k);
if(mid+1<=r)set(p<<1|1,mid+1,pr,l,r,k);
up(p);
}
bool query(int p,int pl,int pr,int l,int r){//增大递归开销
if(l<=pl&&pr<=r)return t[p].value;
down(p);
int mid=pl+pr>>1;
if(l<=mid&&query(p<<1,pl,mid,l,r))return true;
if(mid+1<=r&&query(p<<1|1,mid+1,pr,l,r))return true;
return false;
}
void build(int p,int l,int r){
t[p]={false,-1};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
}t[31];
int n;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int q;
scanf("%d %*d %d",&n,&q);
for(int i=1;i<=30;i++)t[i].build(1,1,n);
t[1].set(1,1,n,1,n,true);
while(q--){
int a,b,c;
char ch;
cin>>ch>>a>>b;
if(a>b)swap(a,b);
switch(ch){
case 'C':
scanf("%d",&c);
for(int i=1;i<=30;i++){
t[i].set(1,1,n,a,b,i==c);
}
break;
case 'P':
int ans=0;
for(int i=1;i<=30;i++){
ans+=t[i].query(1,1,n,a,b);
}printf("%d\n",ans);
break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
状态压缩
既然我们是在卡空间，那么不难发现 bool 其实是极度浪费空间的——$1\text{Byte}=8\text{bit}$，而 bool 占用 $1\text{Byte}$ 却只用了 $1\text{bit}$，即 $\dfrac18$。
因此我们考虑状态压缩。
不难发现，$T\leq30$，因此我们可以将 $30$ 棵线段树压缩为 $1$ 棵线段树，存储的状态表示 $30$ 种颜色。
使用一个 int 变量 $value$，value&(1<<i) 表示区间中颜色 $i$ 是否存在。
AC 代码
警告：请不要把位运算符
| 写为逻辑运算符 ||1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5,T=30;
struct seg{
struct node{
int l,r;
int value;
int tag;
}t[4*N+1];
void up(int p){
t[p].value = t[p<<1].value|t[p<<1|1].value;
}
void down(int p){
if(t[p].tag){
t[p<<1].value=1<<t[p].tag-1;
t[p<<1].tag=t[p].tag;
t[p<<1|1].value=1<<t[p].tag-1;
t[p<<1|1].tag=t[p].tag;
t[p].tag=0;
}
}//涂上颜色k
void set(int p,int l,int r,int k){
if(l<=t[p].l&&t[p].r<=r){
t[p].value=(1<<k-1);
t[p].tag=k;
return;
}
down(p);
if(l<=t[p<<1].r)set(p<<1,l,r,k);
if(t[p<<1|1].l<=r)set(p<<1|1,l,r,k);
up(p);
}
int query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r)return t[p].value;
down(p);
int ans=0;
if(l<=t[p<<1].r)ans=query(p<<1,l,r);
if(t[p<<1|1].l<=r)ans=ans|query(p<<1|1,l,r);
return ans;
}
void build(int p,int l,int r){
t[p]={l,r,1,0};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
}t;
int n;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int q;
scanf("%d %*d %d",&n,&q);
t.build(1,1,n);
while(q--){
int a,b,c;
char ch;
cin>>ch>>a>>b;
if(a>b)swap(a,b);
switch(ch){
case 'C':
scanf("%d",&c);
t.set(1,a,b,c);
break;
case 'P':
int pl=t.query(1,a,b);
int ans=0;
while(pl){
ans+=(pl&1);
pl>>=1;
}printf("%d\n",ans);
break;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
