第 8 章 集合¶
配套例题：BISHI4 【模板】集合操作、BISHI5 【模板】多重集合操作 来源：菜鸟教程 Python3 集合、Python3 数据结构
set 是「只有键、没有值」的哈希表，对应 C++ 的 std::unordered_set。
它在竞赛里只干两件事，但这两件事出现频率极高：
- \(O(1)\) 判断「见过没有」 —— 判重、访问标记、去重
- 集合运算 —— 交并差，一行代替一个循环
同时，本章要交代一个 Python 相对 C++ 的明确劣势：
标准库里没有有序集合。std::set 的 lower_bound 在 Python 里没有对应物，
本章的两道模板题正好把这个缺口暴露出来。
8.1 创建集合¶
s = set() # ★ 空集合只能这样写
s = {1, 2, 3} # 字面量（非空时才行）
s = set([1, 2, 2, 3]) # {1, 2, 3} 自动去重
s = set("hello") # {'h','e','l','o'} 字符串按字符拆
s = {x * x for x in range(5)} # 集合推导式
{}是空字典，不是空集合。 空集合必须写set()。 这是 Python 语法上一个无法回避的历史包袱（字典比集合先出现，占用了{}）。
集合是无序的，打印顺序和插入顺序无关，也不是排序后的顺序：
绝对不要依赖集合的迭代顺序产生输出。 需要有序输出就
sorted(s)。 而且字符串的哈希每次运行都不同（哈希随机化），本地跑对了 OJ 上可能就是另一个顺序。
8.2 增删查¶
s.add(x) # 添加单个元素，已存在则无操作，O(1)
s.update(iterable) # 批量添加，参数可以是任意可迭代对象
s.update([1, 2], (3,)) # 可以传多个
s.remove(x) # 删除，不存在抛 KeyError
s.discard(x) # 删除，不存在不报错 ← 竞赛里更常用
x = s.pop() # 弹出并删除任意一个元素（弹哪个不由调用者决定，见下），空集合抛 KeyError
s.clear() # 清空
x in s # ★ O(1) 判存在
len(s) # O(1)
| 方法 | 元素不存在时 |
|---|---|
s.remove(x) |
抛 KeyError |
s.discard(x) |
静默忽略 |
s.pop()弹出的是「哈希表里第一个非空槽」，不是随机也不是最小值。 想拿最小值只能min(s)，那是 \(O(n)\)。set没有「取最小」的快捷方式。
8.3 集合运算¶
| 运算 | 运算符 | 方法 | 含义 |
|---|---|---|---|
| 并集 | a \| b |
a.union(b) |
在 a 或 b 中 |
| 交集 | a & b |
a.intersection(b) |
同时在 a 和 b 中 |
| 差集 | a - b |
a.difference(b) |
在 a 但不在 b |
| 对称差 | a ^ b |
a.symmetric_difference(b) |
恰好在一个里面 |
| 子集 | a <= b |
a.issubset(b) |
a 的元素都在 b 里 |
| 真子集 | a < b |
— | 子集且不相等 |
| 超集 | a >= b |
a.issuperset(b) |
|
| 不相交 | — | a.isdisjoint(b) |
交集为空 |
a = set("abracadabra") # {'a','r','b','c','d'}
b = set("alacazam") # {'a','l','c','z','m'}
a - b # {'r','d','b'}
a | b # {'a','c','r','d','b','m','z','l'}
a & b # {'a','c'}
a ^ b # {'r','d','b','m','z','l'}
每个运算都有原地版本（修改左操作数，省掉一次分配）：
a |= b # a.update(b)
a &= b # a.intersection_update(b)
a -= b # a.difference_update(b)
a ^= b # a.symmetric_difference_update(b)
运算符版要求两边都是
这是个高频小坑：从set，方法版接受任意可迭代对象：list直接做并集要么先set(...)，要么用方法版。
集合运算的复杂度：a & b 只需遍历较小的那个集合，a - b 要遍历整个 a，
a | b 两个都要遍历；具体量级见 8.7 的复杂度表。
用运算符一行写完，比手写循环快很多（全在 C 层）。
# 求两个数组的公共元素
common = set(a) & set(b) # ✅ O(n + m)
common = [x for x in a if x in b] # ❌ O(n·m)，b 是 list 时是 O(n) 查找
集合的比较是「偏序」¶
< <= 判的是包含关系，不是大小关系。所以两个集合可能互不可比：
因此
sorted(list_of_sets)是没有意义的（排序要求全序）。 需要排序请显式给key。
8.4 in 是 \(O(1)\)：最重要的一条¶
这是整本书最值钱的性能结论，03-运算符与位运算 已经强调过一次， 这里再说一遍：
| 容器 | x in c |
说明 |
|---|---|---|
list / tuple |
\(O(n)\) | 逐个比较 |
str |
\(O(n \cdot m)\) 最坏 | 子串搜索 |
set / frozenset |
\(O(1)\) 平均 | 算一次哈希 |
dict |
\(O(1)\) 平均 | 查的是键 |
range |
\(O(1)\) | 数学公式判断 |
# ❌ O(n²)，n = 1e5 必然 TLE
seen = []
for x in a:
if x not in seen:
seen.append(x)
# ✅ O(n)
seen = set()
for x in a:
if x not in seen:
seen.add(x)
只要写出
in且它在循环里，就停下来问一句：右边是set还是list？ 这是 Python 算法题最高频的 TLE 原因，没有之一。
同样的道理，删除也要注意：
8.5 去重¶
b = list(set(a)) # 去重，但顺序被打乱
b = sorted(set(a)) # 去重 + 排序 —— 离散化的标准写法
b = list(dict.fromkeys(a)) # ★ 保序去重（利用 dict 3.7+ 插入有序）
三者的取舍：
| 写法 | 保序 | 复杂度 | 用途 |
|---|---|---|---|
list(set(a)) |
❌ | \(O(n)\) | 只关心「有哪些元素」 |
sorted(set(a)) |
排序 | \(O(n \log n)\) | 离散化、需要有序输出 |
list(dict.fromkeys(a)) |
✅ 首次出现顺序 | \(O(n)\) | 题目要求「按首次出现顺序」 |
判断数组是否有重复元素：
8.6 元素必须可哈希¶
和字典的键一样，集合元素必须是不可变对象：
s = {1, "a", (1, 2), frozenset({3})} # ✅
s.add([1, 2]) # ❌ TypeError: unhashable type: 'list'
s.add({1: 2}) # ❌ unhashable type: 'dict'
s.add({1, 2}) # ❌ unhashable type: 'set'
所以集合不能直接存集合——这正是 frozenset 存在的理由。
frozenset：不可变的集合¶
fs = frozenset([1, 2, 3])
fs2 = frozenset("abc")
fs.add(4) # ❌ AttributeError：没有 add
fs | {4} # ✅ 集合运算都支持，返回新的 frozenset
hash(fs) # ✅ 可哈希
frozenset 支持所有只读操作（| & - ^ in len <= …），
没有任何修改方法。它的唯一价值是可哈希：
d = {}
d[frozenset({1, 2})] = "组合 {1,2}" # ✅ 集合当字典键
d[frozenset({2, 1})] = "会覆盖上一行" # 集合无序，{1,2} 和 {2,1} 是同一个键
states = set()
states.add(frozenset(cur)) # 集合的集合：搜索中的状态判重
竞赛里
frozenset用得不多，因为「元素集合」的状态几乎都能用 整数位掩码表示，而位掩码更快更省：只有元素不是「\(0..n-1\) 的小整数」时才考虑mask = 0 mask |= 1 << i # 加入元素 i if mask >> i & 1: ... # 判断是否包含 i vis.add(mask) # 状态判重，整数键比 frozenset 快好几倍frozenset。 位掩码技巧见 46-位运算。
8.7 复杂度、内存与「Python 没有有序集合」¶
复杂度表¶
| 操作 | 平均 | 最坏 |
|---|---|---|
s.add(x) / s.discard(x) / x in s |
\(O(1)\) | \(O(n)\) |
len(s) |
\(O(1)\) | \(O(1)\) |
a \| b |
\(O(\|a\|+\|b\|)\) | |
a & b |
\(O(\min(\|a\|,\|b\|))\) | |
a - b |
\(O(\|a\|)\) | |
min(s) / max(s) |
\(O(n)\) | |
sorted(s) |
\(O(n \log n)\) | |
| 遍历 | \(O(n)\) |
内存¶
一个元素在 set 里大约占 32–60 字节（哈希值 + 指针 + 保留的空槽）。
\(10^6\) 个整数的 set 要 30–60 MB，而 bytearray(10**6) 只要 1 MB。
值域已知且不大时，用
值域大、稀疏时才用bytearray或list代替set：set。
与 C++ 容器的对照¶
| 需求 | C++ | Python |
|---|---|---|
| 判存在 | unordered_set |
✅ set |
| 去重 | unordered_set |
✅ set |
| 计数（multiset 语义） | multiset / unordered_map |
✅ Counter / dict |
| 按大小遍历 | std::set |
❌ 只能 sorted(s)，\(O(n \log n)\) |
前驱 / 后继（lower_bound） |
std::set \(O(\log n)\) |
❌ 没有 |
| 静态数据上二分 | lower_bound |
✅ bisect（要求已排序） |
Python 标准库里没有平衡树。 需要「动态插入删除 + 查前驱后继」时，只有这几条路：
| 方案 | 复杂度 | 适用 |
|---|---|---|
排好序的 list + bisect |
查 \(O(\log n)\)，改 \(O(n)\) | 元素少、或只查不改 |
| 树状数组 / 线段树（值域） | \(O(\log V)\) | 首选；值域大或含负数就先离散化 |
| 堆 + 懒删除 | 均摊 \(O(\log n)\) | 只需要取最小 / 最大 |
sortedcontainers.SortedList |
\(O(\sqrt[3]{n})\) 级 | 第三方库，OJ 不保证有，别赌 |
8.8 例题¶
BISHI4 【模板】集合操作（简单）¶
维护一个初始为空的集合 \(M\)（元素互不相同），\(n \le 10^5\) 次操作，\(0 \le x \le 10^6\)：
1 x插入（已存在则忽略）、2 x删除（不存在则忽略）、3 x查询是否存在（YES/NO）、4查询集合大小、5 x查询前驱（小于 \(x\) 的最大数，不存在输出-1）、6 x查询后继（大于 \(x\) 的最小数，不存在输出-1）。 题面见 BISHI4 原题（牛客）。
这题是一面镜子，照出 Python set 的能力边界。
操作 1–4 正好是 set 的看家本领，各一行：
| 操作 | Python | 复杂度 |
|---|---|---|
1 x 插入 |
s.add(x) |
\(O(1)\) |
2 x 删除 |
s.discard(x)（不能用 remove，会抛异常） |
\(O(1)\) |
3 x 查询 |
"YES" if x in s else "NO" |
\(O(1)\) |
4 大小 |
len(s) |
\(O(1)\) |
5 x 前驱 |
没有对应方法 | — |
6 x 后继 |
没有对应方法 | — |
操作 5、6 就是 C++ 的 s.lower_bound(x)，set 做不到。
用 max(v for v in s if v < x) 是 \(O(n)\)，\(10^5\) 次查询就是 \(10^{10}\)，必挂。
解法：离散化 + 树状数组。
- 离散化：把稀疏的大值域换成 0 到 m-1 的连续下标，之后就能用数组代替字典。
- 树状数组（Binary Indexed Tree，也叫 Fenwick 树）：一个数组，第 i 个位置负责一段
长度为
lowbit(i)的区间和，于是单点修改和前缀和查询都只需沿 \(O(\log V)\) 个位置走一遍。 完整推导见 39-树状数组与线段树。
树状数组在这里维护「某个值是否在集合中」的前缀和：
- 前驱：设 $k = $ 严格小于 \(x\) 的元素个数。若 \(k = 0\) 则无前驱；否则答案是第 \(k\) 小的元素。
- 后继：设 $c = $ 小于等于 \(x\) 的元素个数。若 \(c = |M|\) 则无后继；否则答案是第 \(c+1\) 小的元素。
「求第 \(k\) 小」用树状数组上倍增：从最大的 2 的幂步长起步，能往右跳就跳、 跳过头就换更小的步长，只需对数级步数就能定位到目标位置。
树状数组开在离散化后的下标上，而不是原始值域上。 题面虽然写了 \(0 \le x \le 10^6\)，但实测数据里有负数（见下面第 1 个坑）， 直接按值域开数组会当场出事。好在这题是离线的——\(n\) 行操作可以一次读完， 把所有出现过的 \(x\) 去重排序（至多 \(10^5\) 个）就与原始值域彻底脱钩了。 而且前驱/后继的答案必然是某个插入过的值，一定在离散化表里，所以答案不会丢。
import sys
def main():
# 按行读：操作 4 那行只有一个数，按行 split 后看长度对两种写法都免疫
lines = sys.stdin.buffer.read().split(b"\n")
n = int(lines[0])
# 第一遍：读出操作，顺便收集所有出现过的 x
ops = []
vals = []
for li in range(1, n + 1):
parts = lines[li].split()
op = parts[0]
if op == b"4": # 操作 4 只查大小，这行没有第二个数
ops.append((4, 0))
else:
x = int(parts[1])
ops.append((int(op), x))
vals.append(x)
uniq = sorted(set(vals)) # 下标 -> 原值
rank = {v: i for i, v in enumerate(uniq)} # 原值 -> 下标
m = len(uniq)
V = 1
while V < m + 1: # 取 2 的幂，方便树状数组上倍增
V <<= 1
tree = [0] * (V + 1) # 树状数组：下标 i 对应位置 i+1
present = bytearray(m) # present[i] = 1 表示第 i 个值在集合里
size = 0
out = []
for op, x in ops:
if op == 4:
out.append(str(size))
continue
idx = rank[x]
if op == 1:
if not present[idx]: # 已存在则忽略
present[idx] = 1
size += 1
# 树状数组下标从 1 开始，所以是 idx + 1；
# i & (-i) 取 i 最低位的 1（lowbit，见 03 章 3.6），
# 它正是树状数组每次跳跃的步长——沿着它一路往右加，
# 就把所有包含该位置的区间和都更新到了
i = idx + 1
while i <= V:
tree[i] += 1
i += i & (-i)
elif op == 2:
if present[idx]: # 不存在则忽略
present[idx] = 0
size -= 1
i = idx + 1
while i <= V:
tree[i] -= 1
i += i & (-i)
elif op == 3:
out.append("YES" if present[idx] else "NO")
else:
# k = 严格小于 x 的元素个数，即下标 [0, idx-1] 的前缀和
k = 0
i = idx
while i > 0: # 查前缀和：反过来一路减 lowbit，把若干段拼起来
k += tree[i]
i -= i & (-i)
if op == 6: # 后继 = 第 (小于等于 x 的个数 + 1) 小
k += present[idx] + 1
if k > size:
out.append("-1")
continue
else: # 前驱 = 第 k 小
if k == 0:
out.append("-1")
continue
# 树状数组上倍增求第 k 小：step 从 V 起步（V 取成 2 的幂正是为了这里），
# 每轮试着往右跳 step；判据用严格的 < 而不是 <=，
# 这样前缀和恰好等于 k 时不会跳过头，最终停在最靠左的合法位置
pos = 0
rem = k
step = V
while step:
nxt = pos + step
if nxt <= V and tree[nxt] < rem:
pos = nxt
rem -= tree[nxt]
step >>= 1
out.append(str(uniq[pos])) # 位置 pos+1 对应下标 pos
sys.stdout.write("\n".join(out) + "\n")
main()
复杂度：\(O(n \log n)\)，实测 \(10^5\) 次操作约 0.2 秒。
四个坑：
-
题面给的值域不可信。题面写 \(0 \le x \le 10^6\)，实测数据里却有负数。 若按值域开数组，负下标在 Python 里不会报错而是从尾部绕回去， 于是
present[x]静静地读到了别的值；更隐蔽的是树状数组的i += i & (-i)：\(i\) 为负时会一路爬到 \(i = 0\)，而 \(0\ \&\ 0 = 0\)， 循环再也走不动——死循环，判成超时而不是报错，极难定位。 离线题遇到「值域看着很小」的诱惑，先想想离散化值不值这点代价。 -
输入格式不统一，而且 BISHI4 与 BISHI5 还不一样。 BISHI4 的操作 4 那一行只有一个数（题面写「对于操作 4，输入两个整数 opt」是笔误， 看示例即知），其余操作有两个；而 BISHI5 的题面明确写「每行输入两个整数 opt 和 x」， 操作 4 写作
4 0。
结论是：按行读、
直接split()后看长度才是对两题都安全的写法：op, x = line.split()会在 BISHI4 的操作 4 上抛ValueError； 而「token 流 + 遇到操作 4 就不读 x」虽然对 BISHI4 正确， 却依赖「测试数据里操作 4 一定不带第二个数」这个未被题面担保的假设—— 一旦某个测试点写成4 0，游标就会整体错位，且错得毫无征兆。 按行解析对两种写法都免疫，这是本题唯一稳妥的选择。
-
「已存在则忽略」必须真的判一下。
set天然满足，但树状数组不判就会重复计数。 这里用present这个bytearray同时承担「\(O(1)\) 判存在」和「防重复更新」两个职责。 -
前驱是「严格小于」，后继是「严格大于」。查询
5 x时如果 \(x\) 本身在集合里， 它不能算作自己的前驱。代码里那段while i > 0的前缀和统计的是离散化下标 \([0, idx-1]\)，天然排除了 \(x\) 自己； 后继则要+ present[idx]把 \(x\) 自己跳过去。
另一种偷懒写法：
present已经是按下标排好序的bytearray， 直接用它的rfind/find做 C 级别的线性扫描：写起来只要两行，j = present.rfind(1, 0, idx) # 前驱：idx 左边最后一个 1 # rfind 的第一个参数可以直接传 0-255 的整数，底层走 memchr pre = uniq[j] if j >= 0 else -1 # 注意要映射回原值，不能直接输出下标 j = present.find(1, idx + 1) # 后继：idx 右边第一个 1 suc = uniq[j] if j >= 0 else -1memchr的常数极小，随机数据下比树状数组还快。 但它最坏是 \(O(n)\)——出题人只要构造「集合很空 + 反复查一头一尾的前驱后继」就能卡掉。 笔试时间紧可以先交这个版本试试，正式解法还是树状数组。这里也顺带说明：离散化之后
rfind返回的 \(-1\) 是「没找到」， 而题目要求输出的 \(-1\) 是「前驱不存在」，两者恰好撞在一起纯属巧合； 若某个测试点真的插入了 \(-1\) 这个值，直接把下标当答案输出就会错。本书配套题解用的是另一种解法。 上面的树状数组是最通用、最值得先掌握的写法（\(O(\log n)\)，且能顺带支持「第 \(k\) 小」）。 但
solutions/BISHI4.py实际提交的是两级位图： 同样先离散化，再把下标区间切成每块 1024 个，每块用一个 1024 位的 Python 大整数当位图， 再用一个 summary 整数标记哪些块非空。 插入/删除/存在性/前驱/后继全部 \(O(1)\)——因为每步只是几次大整数位运算， 整个循环被压进了 CPython 的 C 层。 树状数组版是 \(O(n \log n) \approx 1.7 \times 10^6\) 次纯 Python 循环迭代， 实测 \(10^5\) 次操作约 0.2 秒；位图版仅 0.11 秒。 题面给的是「其他语言 2 秒」，两个版本都过得很轻松—— 这个对比的意义不在于「必须用位图」，而在于差距的来源。这个对比是 Python 算法优化的典型样本：降低渐进复杂度不一定比消灭 Python 层循环更有效。 详见 21-复杂度与Python性能 §21.4。
BISHI5 【模板】多重集合操作（简单）¶
和 BISHI4 几乎一样，但集合变成多重集合（元素可重复），且 \(|x| \le 10^6\)（可能是负数）：
1 x插入、2 x删除一个、3 x查询 \(x\) 的个数、4 x查询总个数（含重复）、5 x前驱、6 x后继。 题面见 BISHI5 原题（牛客）。
和 BISHI4 的三个差异：
| 差异 | 处理 |
|---|---|
| 元素可重复 | set 换成 dict（值 → 次数），即 Counter 的手写版 |
| \(x\) 可能为负 | 整体平移 v = x + 10**6，值域变成 \([0, 2 \times 10^6]\) |
| 每行都是两个数 | 操作 4 也带一个（无意义的）参数，读法反而更简单 |
BISHI4 的教训是「题面值域不可信」，这里为什么敢直接按值域开数组？ 因为 BISHI5 的题面明确写了 \(x\) 可能为负且绝对值不超过 \(10^6\)，实测数据也吻合， 平移之后下标一定落在 \([0, 2 * 10^6]\) 内。 只要对值域没把握，退回 BISHI4 的离散化写法永远安全，代价不过是一次
sorted(set(...))。
前驱 / 后继只关心「哪些值出现过」，和出现几次无关，
所以树状数组仍然只维护 0/1 的「是否存在」，在计数从 \(0 \to 1\) 时 +1、从 \(1 \to 0\) 时 -1。
import sys
def main():
data = sys.stdin.buffer.read().split()
p = 0
n = int(data[p]); p += 1
OFF = 10 ** 6 # x 可能为负，整体平移
V = 1 << 21 # 2097152 > 2*10^6
tree = [0] * (V + 1) # 只记录「某个值是否出现过」，供前驱后继使用
cnt = {} # 值 -> 出现次数
total = 0 # 含重复的总个数
out = []
for _ in range(n):
op = data[p]; x = int(data[p + 1]); p += 2
v = x + OFF
if op == b"1":
c = cnt.get(v, 0)
cnt[v] = c + 1
total += 1
if c == 0: # 0 -> 1，值第一次出现
i = v + 1
while i <= V:
tree[i] += 1
i += i & (-i)
elif op == b"2":
c = cnt.get(v, 0)
if c: # 不存在则忽略
total -= 1
if c == 1: # 1 -> 0，值彻底消失
del cnt[v]
i = v + 1
while i <= V:
tree[i] -= 1
i += i & (-i)
else:
cnt[v] = c - 1
elif op == b"3":
out.append(str(cnt.get(v, 0)))
elif op == b"4":
out.append(str(total))
else:
# k = 严格小于 v 的「不同值」个数，即下标 [0, v-1] 的前缀和；
# i -= i & (-i) 沿 lowbit 往左拆区间，把若干段和拼成前缀和
k = 0
i = v
while i > 0:
k += tree[i]
i -= i & (-i)
distinct = len(cnt) # 树状数组里一共有多少个 1
if op == b"6":
# 后继 = 第 (小于等于 v 的个数 + 1) 小；v 自己在集合里就要多跳一格
k += (1 if v in cnt else 0) + 1
if k > distinct: # 超出不同值总数，说明右边没有元素了
out.append("-1")
continue
else:
if k == 0: # 左边一个都没有，前驱不存在
out.append("-1")
continue
# 倍增求第 k 小，判据用严格的 < ，保证停在最靠左的合法位置
pos = 0
rem = k
step = V
while step:
nxt = pos + step
if nxt <= V and tree[nxt] < rem:
pos = nxt
rem -= tree[nxt]
step >>= 1
out.append(str(pos - OFF)) # 别忘了平移回去
sys.stdout.write("\n".join(out) + "\n")
main()
复杂度：\(O(n \log V)\)，实测 \(10^5\) 次操作约 0.15 秒。
四个坑：
-
负数下标。Python 的
a[-1]不报错而是访问末尾（见 05-列表）， 忘记平移会得到毫无规律的错误答案，还很难查。看到 \(|x| \le 10^6\) 就要条件反射地想到OFF。 -
判断「有没有后继」用的是
distinct而不是total。 树状数组里存的是不同值的个数，拿含重复的total去比会误判。 -
删除到 0 时必须
del cnt[v]，否则len(cnt)会把计数为 0 的键也算进去。 （用Counter时更要注意——c[x] -= 1减到 0 甚至负数，键都还在。） -
total单独维护。sum(cnt.values())是 \(O(n)\)，每次操作 4 都算一遍就变 \(O(n^2)\)。
能不能直接用
Counter？ 操作 1–4 完全可以：前驱后继照样得靠树状数组。from collections import Counter c = Counter() c[x] += 1 # 插入 if c[x]: c[x] -= 1 # 删除一个（注意别减成负数） c[x] # 查询个数，不存在返回 0 sum(c.values()) # 总数 —— 但这是 O(n)，要自己维护计数器Counter当多重集合用的完整讨论见 34-集合与多重集合。
8.9 本章速查¶
| 场景 | 写法 |
|---|---|
| 空集合 | set()，{} 是空字典 |
| 判存在 | x in s，\(O(1)\) ← 最重要的一条 |
| 安全删除 | s.discard(x)（remove 会抛 KeyError） |
| 去重 | set(a) |
| 去重 + 排序（离散化） | sorted(set(a)) |
| 保序去重 | list(dict.fromkeys(a)) |
| 判有无重复 | len(set(a)) != len(a) |
| 公共元素 | set(a) & set(b) |
| 只在 a 中的 | set(a) - set(b) |
与 list 做集合运算 |
用方法版 s.union(lst)，运算符要求两边都是 set |
| 值域小的标记数组 | bytearray(n)，比 set 省 30 倍内存且更快 |
| 集合当键 / 集合的元素 | frozenset(...)；小整数集合优先用位掩码 |
| 状态判重 | 优先整数位掩码，其次 frozenset |
| 取最小 / 最大 | min(s) / max(s)，\(O(n)\)，别在循环里用 |
| 前驱 / 后继 | set 不支持；离线题用「离散化 + 树状数组」，静态数据用 bisect |
| 有序遍历 | sorted(s)，别指望迭代顺序 |