题解：P10208 [JOI 2024 Final] 礼物交换

· · 题解

首先二分图匹配的模型是显然的。我们对于一个 A_i，将其向所有满足 B_j\leq A_i 且 i\neq j 的 B_j 连边，然后对每个询问做最大匹配即可。

考虑怎样才会不合法。利用霍尔定理，合法的充要条件是任意大小为 k 的 B 集合的邻域大小都不能小于 k。这里可以先考虑一些极端情况：对于 A 最大的 x，若不存在一个 A_i>B_x，则 x 无法收到礼物，一定不合法。也即，若我们把 [B_i,A_i] 看作一条线段，则需要保证最大的那一条线段与其它线段有交。

考虑扩展这一结论：有合法解的条件是任意线段都与其它线段有交。这里的必要性比较容易证明：假设线段 [A_i,B_i] 与其它线段无交，则拿出坐标小于等于这个线段的所有线段（含其本身）的集合 S，考虑任意 x\in S 对应的 B 处点集的邻域，由于自己不和自己连边，显然有邻域大小为 |S|<|S|+1，故一定不存在完美匹配。

接下来考虑这个结论的充分性：对于任意一个 B 集合，取出 B_x 最小的那一个 x，则 B_x 一定向集合内的其它元素的 A 部有连边，则邻域大小至少为 |B|-1。又因为一定存在线段与 [B_x,A_x] 相交，不妨假设 [B_y,A_y] 与其相交，讨论相交情况：

  1. 若 B_y\leq B_x，则 y 一定不在当前 B 集合内。由于相交一定有 A_y\geq B_x，即 B_x 一定与 A_y 相连，可给邻域额外贡献 1，合法。
  2. 若 B_y\geq B_x，由于相交，一定有 B_y\leq A_x，此时 B_x 一定与 A_y 相连。讨论下面两种情况：
    • 若 y\in B，则 B_y 一定连边向 A_x，可给邻域额外贡献 1，合法。
    • 若 y\notin B，则 A_y 可给邻域额外贡献 1，合法。

根据霍尔定理，任意一个 B 集合的邻域大小都至少为 |B|，故存在完美匹配。充分性得证。

于是可以预处理求出 L_i 表示每个线段标号左侧首个与 i 相交的标号。从左往右扫一遍，等价于区间覆盖，求区间最大值。R_i 同理。

最终就变成每次询问给定一个 l,r，不合法的情况即为存在一个 i 满足 L_i<l\leq i\leq r<R_i，即有若干左上角在 (L_i+1,i)，右下角在 (i,R_i-1) 位置的矩形，每次询问判断点 (l,r) 是否被某个矩形覆盖，是则不合法，输出 No，离线后扫描线即可。