自动搬运

查看原文

来自洛谷，原作者为

	naoliaok_lovely 人家只是个珂爱的妹子啦

搬运于2025-08-24 23:06:37，当前版本为作者最后更新于2024-12-23 15:22:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道有趣的思维题，不过好像比较板。

先考虑题目的朴素版：已知若干集合（相较于原题目少了区间补集的限制），求最早有一个人发现自己不在某集合内的时间。
设 $f(S)$ 表示包含所有 $S$ 中的人的集合构成的总集合。讨论在每个时间结束的条件：

• 第一轮结束，显然条件为 $\exist i,f(\{i\})=\varnothing$。
• 第二轮结束，此时意味着所有的人都至少被一个集合包含。考虑 $\exist i,j,f(\{i,j\})=\varnothing$，此时在 $i$ 的眼中，如果包含 $i$ 的集合是所有集合，就没有集合能够包含 $j$，那么 $j$ 会在第一轮报告。这说明包含 $i$ 的集合并不是所有集合，于是 $i$ 会在第二轮报告，同理 $j$ 也会在第二轮报告。
• 第三轮结束，不难证明充要条件是 $\exist i,j,k,f(\{i,j,k\})=\varnothing$。
• ……

于是我们得到结论：第 $i$ 轮结束的充要条件是 $\exist f(\{x_1,x_2\dots,x_i\})=\varnothing$，且报告的人的集合为满足上述条件的并。

回到原问题，即求出最少的人数，使得每一个区间的补集都不能完全包含之。这又等价于每一个区间都至少包含一个人。这是一个十分基础的问题，贪心扫一遍即可求出最小人数。还要求所有合法构造的人集合的并，这个就左右分别扫一遍，记录下两次贪心的方案，判断在强制选 $i$ 号点之后能取到最小人数是不是刚刚的答案即可。

时间复杂度 $O(n\log n)$。