P1558 色板游戏

Description

色板长度为L,L是一个正整数,所以我们可以均匀地将它划分成L块1厘米长的小方格。并从左到右标记为1, 2, … L。

现在色板上只有一个颜色,老师告诉阿宝在色板上只能做两件事:

“C A B C” 指在A到 B 号方格中涂上颜色 C。
“P A B” 指老师的提问:A到 B号方格中有几种颜色。
学校的颜料盒中一共有 T 种颜料。为简便起见,我们把他们标记为 1, 2, … T. 开始时色板上原有的颜色就为1号色。 面对如此复杂的问题,阿宝向你求助,你能帮助他吗?

Solution

因为只有30种颜色, 所以可以用一个int来表示, 线段树的每个节点维护的是区间颜色种类数的整数表示.

Code

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
#include <string>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using std:: min;
using std:: max;
struct Node {
int status, flag;
Node *ls, *rs;
Node () { status = 1, flag = 0, ls = rs = NULL; }
int Result() { return __builtin_popcount(status); }
void update() { status = ls->status | rs->status; }
void Merge(int k) { flag = k, status = k; }
void Down() { if (flag) ls->Merge(flag), rs->Merge(flag), flag = 0; }
};
class STree {
private:
Node *root; int n;
void build(int l, int r, Node *node) {
if (l == r) return ;
int mid = l + r >> 1;
node->ls = new Node();
node->rs = new Node();
build(l, mid, node->ls);
build(mid + 1, r, node->rs);
node->update();
}
void modify(int l, int r, int L, int R, Node* node, int k) {
if (l >= L and r <= R)
return node->Merge(k);
int mid = l + r >> 1;
node->Down();
if (L <= mid) modify(l, mid, L, R, node->ls, k);
if (R > mid) modify(mid + 1, r, L, R, node->rs, k);
node->update();
}
int query(int l, int r, int L, int R, Node* node) {
if (l >= L and r <= R)
return node->status;
node->Down();
int mid = l + r >> 1; int res = 0;
if (L <= mid) res |= query(l, mid, L, R, node->ls);
if (R > mid) res |= query(mid + 1, r, L, R, node->rs);
return res;
}
public:
STree() { root = new Node(); }
void build(int _) { n = _; build(1, n, root); }
void modify(int l, int r, int k) { modify(1, n, l, r, root, k); }
int query(int l, int r) {
if (l > r) std:: swap(l, r);
return __builtin_popcount(query(1, n, l, r, root));
}
};
int main () {
int n, c, m;
scanf("%d%d%d", &n, &c, &m);
STree* T = new STree();
T->build(n);
for (int i = 0; i < m; i += 1) {
std:: string opt; int l, r, k;
std:: cin >> opt; scanf("%d%d", &l, &r);
if (opt[0] == 'C') {
scanf("%d", &k);
T->modify(l, r, 1 << k - 1);
}
else printf("%d\n", T->query(l, r));
}
return 0;
}
-------------本文结束感谢您的阅读-------------