题面
注意到$T\leq 30$
所以可以把存在的颜色集合压成一个int
于是可以区间赋值线段树做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
using namespace std;
int tag[400010], sum[400010];
inline void up(int x) {
sum[x] = sum[x << 1] | sum[x << 1 | 1];
}
inline void down(int x) {
if(tag[x]) {
sum[x << 1] = sum[x << 1 | 1] = sum[x];
tag[x << 1] = tag[x << 1 | 1] = 1;
tag[x] = 0;
}
}
inline void add(int x, int l, int r, int L, int R, int k) {
if(l > R || L > r) return;
if(L <= l && r <= R) {
tag[x] = 1;
sum[x] = 1 << (k - 1);
return;
}
int mid = l + r >> 1;
down(x);
add(x << 1, l, mid, L, R, k);
add(x << 1 | 1, mid + 1, r, L, R, k);
up(x);
}
inline int get(int x, int l, int r, int L, int R) {
if(l > R || L > r) return 0;
if(L <= l && r <= R) return sum[x];
int mid = l + r >> 1;
down(x);
return get(x << 1, l, mid, L, R) | get(x << 1 | 1, mid + 1, r, L, R);
}
int n, m;
inline void build(int x, int l, int r) {
if(l == r) {
sum[x] = 1;
return;
}
int mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
up(x);
}
int sze[256];
int main() {
for(int i = 1; i < 256; i++) sze[i] = sze[i >> 1] + (i & 1);
scanf("%d%*d%d", &n, &m);
build(1, 1, n);
for(int i = 1; i <= m; i++) {
int l, r, c;
char opt;
scanf("%s%d%d", &opt, &l, &r);
if(l > r) swap(l, r);
if(opt == 'P') {
int cnt = 0, ans = get(1, 1, n, l, r);
while(ans) cnt += sze[ans & 255], ans >>= 8;
printf("%d\n", cnt);
}
else {
scanf("%d", &c);
add(1, 1, n, l, r, c);
}
}
return 0;
}