用最多 30 位的整数位掩码表示颜色集合，线段树支持区间赋色和颜色种类查询。
OJ: luogu
题目 ID: P1558
难度:普及+/提高
标签:线段树位运算区间赋值python
日期: 2026-07-16 23:59
题意
色板初始全为颜色 1，支持区间涂成一种颜色，以及查询区间内出现了多少种颜色。
思路
颜色 c 用整数 1 << (c-1) 表示，节点保存区间颜色集合，合并就是按位或。区间涂色是赋值懒标记；查询得到集合后用 bit_count() 统计置位数。
Python 知识
- Python 整数位数不限，30 种颜色可自然使用一个位掩码。
mask.bit_count()比手写循环统计二进制位更清楚。- 字节输入直接比较
b'C'、b'P'，避免无必要的字符串解码。
代码
python
import sys
sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
length, colors, operations = map(int, input().split())
tree = [1] * (4 * length)
lazy = [1] * (4 * length)
def apply(node, color_mask):
tree[node] = lazy[node] = color_mask
def push(node):
if lazy[node]:
apply(node * 2, lazy[node])
apply(node * 2 + 1, lazy[node])
lazy[node] = 0
def update(node, left, right, query_left, query_right, color_mask):
if query_left <= left and right <= query_right:
apply(node, color_mask)
return
push(node)
middle = (left + right) // 2
if query_left <= middle:
update(node * 2, left, middle, query_left, query_right, color_mask)
if middle < query_right:
update(node * 2 + 1, middle + 1, right, query_left, query_right, color_mask)
tree[node] = tree[node * 2] | tree[node * 2 + 1]
def query(node, left, right, query_left, query_right):
if query_left <= left and right <= query_right:
return tree[node]
push(node)
middle = (left + right) // 2
answer = 0
if query_left <= middle:
answer |= query(node * 2, left, middle, query_left, query_right)
if middle < query_right:
answer |= query(node * 2 + 1, middle + 1, right, query_left, query_right)
return answer
answers = []
for _ in range(operations):
operation = input().split()
if operation[0] == b'C':
left, right, color = map(int, operation[1:])
if left > right:
left, right = right, left
update(1, 1, length, left, right, 1 << (color - 1))
else:
left, right = map(int, operation[1:])
if left > right:
left, right = right, left
answers.append(str(query(1, 1, length, left, right).bit_count()))
print("\n".join(answers))原有 C++ 版本仍保留：
cpp
/**
* 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-07-16 23:46
* update_at: 2026-07-16 23:46
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}复杂度
每次涂色或查询 O(log L)，空间 O(L)。
总结
当集合大小不超过机器字长时，位掩码能把集合并、交和计数压缩成整数运算。