F. 匹配交友 详细题解

题目核心理解

给定 $n$ 个活动集合 $S_1,S_2,\dots,S_n$，你需要找到一对用户 $(a,b)$，满足以下三个条件：

1. $S_a \cap S_b \neq \emptyset$（两人有共同爱好）
2. $S_a \setminus S_b \neq \emptyset$（$a$ 有 $b$ 没有的爱好）
3. $S_b \setminus S_a \neq \emptyset$（$b$ 有 $a$ 没有的爱好）

如果存在这样的一对，输出 YES 并给出任意一组编号；否则输出 NO。

---

核心思路

1. 关键性质

• 一对用户不是良好匹配，当且仅当： 要么集合不相交，要么一个完全包含另一个。
• 如果不存在任何良好匹配，那么所有集合可以排成一棵包含树： 祖先节点的集合一定包含后代节点的集合。

2. 构造与检验规则

• 把集合按大小从大到小排序。
• 依次为每个集合找一个已处理过、有交集的集合作为父亲。
• 若当前集合不被父亲包含，则这一对就是答案。
• 若同一父亲下的两个孩子有公共活动，则这两个孩子就是答案。
• 全程无矛盾，则输出 NO。

---

算法流程

1. 将所有用户按爱好数量降序排序。
2. 遍历每个用户，为其寻找一个有共同活动的已处理用户作为父亲。
3. 对当前用户 $u$ 和父亲 $p$：
   • 若 $S_u$ 不完全包含在 $S_p$ 中，直接输出 $u$ 和 $p$。
4. 检查同一父亲下的其他子节点：
   • 若有与当前用户共享活动的兄弟节点，直接输出这对兄弟。
5. 遍历结束未找到，输出 NO。

---

公式与复杂度分析

良好匹配条件：

$$S_a\cap S_b \neq \emptyset,\quad S_a\setminus S_b \neq \emptyset,\quad S_b\setminus S_a \neq \emptyset $$

复杂度

• 排序：$O(n\log n)$
• 遍历与检查：$O(\sum k_i)$
• 总时间复杂度：$O\left(\sum k_i \log \sum k_i\right)$

可轻松处理 $n\le 2\times 10^5$、$\sum k_i\le 10^6$ 的数据范围，在 $3$ 秒时限内稳定通过。