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

**题意** ： 在数轴上有 $m$ 个椅子，编号为 $1\sim m$。椅子 $i$ 的坐标为 $i$。 现在有 $n$ 个人要就座，第 $i$ 个人能坐在 $(-\infty,l_i]∪[r_i,+\infty)$ 中的某一把椅子。每一把椅子只能做一个人。 现在要添加一些椅子（可以放在任意实数位置），让所有人都能坐下，求添加椅子的最小数目。 $n,m\leq 2\times 10^5$ ，时限$\texttt{}$。 ------------ 旧文补档。 似乎有贪心做法,但是感觉很难想到啊…… 显然可以建立一个二分图，求出最大匹配，然后给没有匹配上的人加椅子。 于是只需求该二分图的最大匹配数。 然而数据范围较大，直接优化建边配合网络硫算法并不能通过。 考虑 $\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$。 [评测记录](https://atcoder.jp/contests/arc076/submissions/13949247)