AT_arc076_d [ARC076F] Exhausted? 题解 / Hall 定理学习笔记
:::::info[题目基本信息]
考察：图论，线段树，扫描线（
题目简介：
给定一个二分图
数据范围：
-
1\le n,m\le 2\times 10^5 -
\forall i\in[1,n],0\le l_i<r_i\le m+1 ::::: 显然，本题的答案等价于 n-\nu(G) 。
通过尝试众多算法后无果，考虑引入 Hall 定理：
:::::success[Hall 定理]{open} 一个二分图（G=(V_1,V_2,E) ，钦定 $V_1 \le V_2 ），设该二分图的最大匹配为 \nu(G)，则 \nu(G)=V_1 当且仅当： \forall V\subseteq V_1,N_G(V) \ge V ，其中 N_G(V)表示在图 G中 V$ 的邻居点集合。:::::success[证明] 我去他的哪个是充分哪个是必要来着。
- 必要性（后者是前者的必要条件）：
若\exists V\subseteq V_1,|N_G(V)|<|V| ，那么V 的最大匹配小于|V| ，同时由于，每次V 新增一个点的过程中最大匹配最多增加1 ，故\nu(G)<|V_1| ，与条件矛盾，必要性得证。 - 充分性（后者是前者的充分条件）：
若存在二分图\nu(G)<|V_1| 但满足条件\forall V\subseteq V_1,|N_G(V)|\ge|V| ，那么一定有一个左部点不在匹配中，由于满足后者的条件，那么他一定有所连的右部点与其他左部点相连，考虑将这些左部点和原点一起考虑，由于后者条件仍能找到未加进来的右部点，这样不断递归就形成了一条增广路，将其增广可以得到大小为|V_1| 的匹配，与假设矛盾，充分性得证。
证毕。
:::::
Hall 定理还有一条推论：
:::::success[Hall 定理推论]{open}
（引用 Hall 定理内的定义）
::::: :::::success[证明] 还是开拆成不等式。
-
对于一子集 $V\subseteq V_1$ 且 $|V|\ge|N_G(V)|$，该子集内未被匹配的点最少为 $|V|-|N_G(V)|$ 个，那么由于左部点每增加一个点左部点未被匹配的点一定不会减少，所以该二分图未被匹配的点最少为 $\displaystyle\max_{V\subseteq V_2}(|V|-|N_G(V)|)$ 个，小于等于号得证。 -
考虑构造一个新图 $G'=(V_1,V_2',E')$，其中： - $V_2'=V_2\cup D$，其中 $D$ 满足：$|D|=\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|),V_2\cap D=\varnothing$。 - $E'=E\cup\{(u,v)|u\in V_1,v\in D\}$。 对于一子集 $V\subseteq V_1$，它在 $G$ 上的邻居点集 $N_{G'}(V)=N_G(V)\cup D$，那么： $$|N_{G'}(V)|=|N_G(V)\cup D|=|N_G(V)|+\max_{V\subseteq V_1}(|V|-|N_G(V)|)$$ 注意到 $|V|\le|N_G(V)|+\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)=|N_{G'}(V)|$，那么由 Hall 定理可知，$\nu(G')=|V_1|$。 现在将这 $\displaystyle\max_{V\subseteq V_1}(|V|-|N_G(V)|)$ 个点逐一删去，容易发现每次最大匹配最多减少 $1$，那么我们就得到： $$\nu(G)\ge|V_1|-\max_{V\subseteq V_1}(|V|-|N_G(V)|)$$ 大于等于号得证。
原命题得证。
:::::
将引理代入得到本题答案为
但是区间的并（还是两段）并不好做，所以我们考虑容斥成区间的交，容易得到
现在考虑枚举交集，但是你好像忘了什么……
- 交集为空集：
这时需要满足条件\displaystyle\max_{i=1}^nl_i\ge\min_{i=1}^nr_i ，最终答案就是|V|-m ，最大即n-m 。 - 交集非空：
设交集的开左端点为L ，开右端点为R ，那么开左端点为L 的答案就是\displaystyle\max_{R=L+1}^m((\sum_{i=1}^n[l_i\le L\land r_i\ge R])+R-L-1-m) 。 这个可以先对(l_i,r_i) 按第一关键字为l_i 升序，第二关键字为r_i 降序的顺序排序，然后就可以上扫描线加线段树做这题了。
然后就做完了。
时间复杂度为
code