我们只需对每个子集计算至少有两个守卫的时间。离散化之后我们对每个时间单位分别考虑，设该时间单位中工作的守卫集合为 $T$，则我们选择的集合需要满足 $|S\cap T|\ge 2$ 才能计入该时间单位的长度。也即 $S$ 不是某个 $\overline T\cup \{x\}$ 的子集，容斥一下可以变成 $O(k)$ 个“给 $S$ 的所有子集答案加上 $v$”的操作，最后一次 FMT 即可。时间复杂度 $O((\sum c_i+2^k)\cdot k)$。
QOJ.ac
QOJ
Discussion #1058 for Problem #17159. Jewel Guards
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2026-02-19 13:14:16
Last updated: 2026-02-19 13:14:20
题解
Comments
No comments yet.