色板游戏

形式化题目

有一个长度 $L$ 的序列，每个位置有一个颜色（共 $T \leqslant 30$ 种），初始全部为颜色 1。给出 $O$ 次操作：

把区间 $[A,B]$ 内每个位置的颜色改成 $C$ ；
询问区间 $[A,B]$ 内出现了几种不同的颜色。

要求按顺序处理全部操作，并输出每次询问的答案。 $A,B$ 不保证有序。

思路

先看一个可以直接验证想法的朴素解：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-12 22:10
 */
// brute.cpp：小数据暴力解，直接模拟逐格涂色与逐格统计，用来理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int L, T, O;
int board[MAXN]; // board[i] 表示第 i 格当前的颜色编号（1..T）
bool seen[MAXN]; // seen[c] 表示颜色 c 是否在查询区间内出现

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> L >> T >> O;
    for (int i = 1; i <= L; i++)
        board[i] = 1; // 初始整块板都是颜色 1

    for (int i = 1; i <= O; i++) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (a > b) swap(a, b); // 题目不保证 a <= b，需要交换
        if (op == 'C') {
            int c;
            cin >> c;
            // 区间涂色：暴力逐格改颜色。
            for (int j = a; j <= b; j++)
                board[j] = c;
        } else {
            // 区间查询：暴力统计出现了几种颜色。
            memset(seen, 0, sizeof(seen));
            for (int j = a; j <= b; j++)
                seen[board[j]] = true;
            int cnt = 0;
            for (int c = 1; c <= T; c++)
                if (seen[c]) cnt++;
            cout << cnt << '\n';
        }
    }
    return 0;
}

brute.cpp 直接维护数组 board[]：涂色逐格改颜色，查询逐格统计出现的颜色，单次操作 $O(L)$ ，总复杂度 $O(LO)$ ，无法通过 $10^5$ 的数据。

关键观察有两层：

颜色种类很少（ $\leqslant 30$ ）：一个 int（32 位）正好装得下一个颜色集合。颜色 $c$ 用掩码 $1 \ll (c-1)$ 表示，一段区间的颜色集合就是各格掩码的按位或，集合大小就是掩码的置位数（popcount）。
涂色是区间赋值：把一段整块涂成颜色 $c$ ，这段的颜色集合立即变成单色掩码 $1 \ll (c-1)$ ，与区间原来有什么颜色无关。这是标准的赋值型懒标记：整段命中时直接改节点掩码、打标记，不下传；要进子树时再 push 把标记传给儿子。

于是用线段树 + 赋值懒标记：每个节点存这段区间出现的颜色集合掩码，合并用 |；查询把命中节点的掩码按位或起来，最后 __builtin_popcount 数置位数。

数学视角：为什么懒标记能成立

和区间翻转题（如 P3870）同样的代数结构：

查询信息构成幺半群：颜色集合按位或合并，| 满足结合律，且存在单位元 $0$ （空集合），所以 $(2^{[1,T]}, |, 0)$ 是交换幺半群。
涂色是摘要上的自同态：涂色可以仅凭节点摘要结算， $\text{paint}_c(\text{mask}) = 1 \ll (c-1)$ ，并且能与合并操作交换：把左右两半各自涂成 $c$ 再合并，等于把合并结果涂成 $c$ 。这正是"整段涂色不必下到叶子"的数学原因。

一句话概括：查询信息构成幺半群，且区间更新是幺半群上的自同态，就可以用懒标记线段树维护。位掩码版本和普通区间求和版本（rbook 模板 segtree-range-assign）的区别，只是把合并运算 + 换成 |，把 value * len 换成单色掩码本身。

以样例为例，2 格色板每次操作后的真实状态与区间掩码如下：

操作	格 1	格 2	区间掩码	输出
初始	1	1	01 \| 01 = 01
C 1 1 2	2	1	10 \| 01 = 11
P 1 2	2	1	11	2
C 2 2 2	2	2	10 \| 10 = 10
P 1 2	2	2	10	1

观察表中两次查询：区间掩码是各格掩码的按位或，popcount(11) = 2、popcount(10) = 1。涂色把整段集合压成单色掩码后，合并结果立刻反映新颜色，这正是线段树节点 tree 的更新规则。

代码

cpp

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-12 22:10
 * update_at: 2026-08-14 09:00
 */
// P1558 [USACO09OPEN] Count Color S
// 区间赋值 + 区间颜色集合查询（按位或合并）线段树（懒标记）
#include <bits/stdc++.h>
using namespace std;

// 区间赋值 + 区间颜色集合查询线段树（懒标记）
struct SegmentTreeColor {
    // 线段树节点：value 为区间颜色集合掩码，lazy 为待下传的涂色标记
    using T = int;
    struct Node {
        T value = 0;    // 当前区间的真实颜色集合掩码
        T lazy = 0;     // 待下传的涂色值（单色掩码）
        bool has_lazy = false;  // 是否还有未下传的涂色标记

        // 合并两个孩子：颜色集合并集，合并结果不携带懒标记
        Node operator|(const Node &other) const {
            return Node{value | other.value, 0, false};
        }
    };

    // 左儿子 / 右儿子的节点编号
    static int lson(int p) { return p << 1; }
    static int rson(int p) { return p << 1 | 1; }

    // 区间 [l, r] 的中点
    static int mid(int l, int r) { return (l + r) >> 1; }

    int n = 0;              // 区间大小
    vector<Node> tree;      // 线段树数组

    SegmentTreeColor(int n = 0) {
        init(n);
    }

    void init(int size) {
        n = size;
        tree.assign(n * 4 + 5, Node{});
    }

    // 上推：用两个孩子合并出当前节点
    void push_up(int p) {
        tree[p] = tree[lson(p)] | tree[rson(p)];
    }

    // 把节点 p 的整个区间 [l, r] 涂成颜色 value（单色掩码）。
    // 整段变成一种颜色后，集合就是该掩码本身，与区间长度无关，
    // 所以与模板 value * len 的写法不同。
    void apply(int p, int, int, T value) {
        tree[p].value = value;
        tree[p].lazy = value;
        tree[p].has_lazy = true;
    }

    // 下推：把节点 p 的懒标记传给两个孩子
    void push_down(int p, int l, int r) {
        if (!tree[p].has_lazy || l == r) return;

        int m = mid(l, r);
        apply(lson(p), l, m, tree[p].lazy);
        apply(rson(p), m + 1, r, tree[p].lazy);
        tree[p].has_lazy = false;
    }

    // 用数组 a 建树（a[i] 是位置 i 的颜色集合掩码，这里全部是颜色 1）
    void build(const vector<T> &a, int l, int r, int p = 1) {
        if (l == r) {
            tree[p].value = a[l];
            return;
        }
        int m = mid(l, r);
        build(a, l, m, lson(p));
        build(a, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间涂色：把 [ql, qr] 全部涂成颜色 value（单色掩码）
    void assign_range(int ql, int qr, T value, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) {
            apply(p, l, r, value);
            return;
        }

        push_down(p, l, r);
        int m = mid(l, r);
        if (ql <= m) assign_range(ql, qr, value, l, m, lson(p));
        if (qr > m) assign_range(ql, qr, value, m + 1, r, rson(p));
        push_up(p);
    }

    // 区间查询：[ql, qr] 内出现的颜色集合掩码
    T query(int ql, int qr, int l, int r, int p = 1) {
        if (ql <= l && r <= qr) return tree[p].value;

        push_down(p, l, r);
        int m = mid(l, r);
        T answer = 0;
        if (ql <= m) answer |= query(ql, qr, l, m, lson(p));
        if (qr > m) answer |= query(ql, qr, m + 1, r, rson(p));
        return answer;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int L, T, O;
    cin >> L >> T >> O;

    // 初始整块板都是颜色 1，每个位置的颜色集合掩码都是 1
    vector<int> a(L + 1, 1);

    SegmentTreeColor seg(L);
    seg.build(a, 1, L);

    while (O--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (a > b) swap(a, b); // 题目不保证 a <= b，需要交换
        if (op == 'C') {
            int c;
            cin >> c;
            seg.assign_range(a, b, 1 << (c - 1), 1, L); // 颜色 c 用第 c-1 位表示
        } else {
            int mask = seg.query(a, b, 1, L);
            cout << __builtin_popcount((unsigned)mask) << '\n'; // 置位数 = 颜色种类数
        }
    }

    return 0;
}

复杂度

时间：单次操作 $O(\log L)$ ，总 $O(O \log L)$ 。
空间：线段树四倍数组， $O(L)$ 。

总结

这道题是"位掩码 + 区间赋值懒标记"最标准的模板：集合规模不超过机器字长时，用整数位掩码压缩集合，把集合并、交集和计数变成整数运算。涂色是赋值型更新，整段结算后标记直接覆盖；理解了 pull / apply / push 的写法，就掌握了线段树处理区间赋值类问题的核心套路。rbook 的《线段树：区间赋值与区间查询》讲解了同一种 pull / apply / push 模板结构，本解即由该模板（segtree-range-assign）改造而来：合并运算从 + 改成 |，赋值从 value * len 改成单色掩码本身。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19朴素模拟（brute.cpp）
  数组 board[1..L] 逐格涂色 / 逐格统计    O(L) 每次操作
        |
        | 瓶颈：单次操作 O(L)，O 次操作 O(L*O) 太大
        v
关键观察
  颜色数 <= 30：一个 int 位掩码装下整个颜色集合
  区间涂色 = 区间赋值：整段集合变成单色掩码 1 << (c-1)
  区间集合合并 = 按位或
        |
        v
线段树 + 赋值懒标记（main.cpp）
  节点存区间颜色集合掩码 tree[p]（按位或合并）
  懒标记 lazy[p] 存整段待涂的单色掩码（后涂覆盖先涂）
  涂色：整段直接 tree[p] = 单色掩码，打标记，不下传
  查询：遇到标记先下传，再进子树；结果 popcount 即种类数
        |
        v
复杂度 O(O log L)，空间 O(L)

图中三条主线分别对应"暴力在哪里慢"“观察到什么性质”“正式解如何利用这个性质”。位掩码把"一个区间的颜色集合"压缩成一个整数，让合并和统计都是常数时间；懒标记把"整段涂色"这个赋值暂停在节点上，等真正要访问子树时才往下传，让一次操作只走一条树链。

目录

形式化题目

思路

数学视角：为什么懒标记能成立

代码

复杂度

总结

图示解析