[图论记录]AT2645 [ARC076D] Exhausted?

command_block · 2021-05-20 22:10:30 · 个人记录

题意：在数轴上有 m 个椅子，编号为 1\sim m。椅子 i 的坐标为 i。

现在有 n 个人要就座，第 i 个人能坐在 (-\infty,l_i]∪[r_i,+\infty) 中的某一把椅子。每一把椅子只能做一个人。

现在要添加一些椅子（可以放在任意实数位置），让所有人都能坐下，求添加椅子的最小数目。

------------ 旧文补档。似乎有贪心做法,但是感觉很难想到啊…… 显然可以建立一个二分图，求出最大匹配，然后给没有匹配上的人加椅子。于是只需求该二分图的最大匹配数。然而数据范围较大，直接优化建边配合网络硫算法并不能通过。考虑 $\rm Hall$ 定理(的推论)来求解这个二分图最大匹配。 - **结论** ：二分图的最大匹配为 $n-\max\big(|S|-|N(S)|\big)

左侧的 S 不具有任何性质,不好处理。而右侧的 N(S) 总是 [0,L]∩[R,\inf] 的形式。

考虑离散化之后枚举 L,R ,查看哪些点符合条件,复杂至少 O(n^2)。

接下来我们可以钦定 L ,使用数据结构维护 R 的 \max。

维护 |S|

考虑一个人 (l,r) 邻域是 [0,L]∩[R,\inf] 的子集的充要条件 : [l\leq L][R\leq r] (二维数点)。

若 L 向右移动一位,可能会使得一个新的左侧点得以满足 [l\leq L] ,然后这个点会贡献到所有 [R\leq r] 的位置。就是前缀加。
维护 |N(S)|

事先对于每个 R 计算满足 [R\leq p] 的椅子数目,也就是 m-R+1 。

当 L 向右移动一位,同样会使得一个新的椅子满足 [p\leq L] ,触发全局减。
查询

对于一个确定的 L ,合法的 R 必须满足 [L<R] ,于是就相当于区间最大值。

线段树维护即可。注意最后要与 n-m 取个\max。

评测记录