Hall 定理 笔记

邻域 $N(S)$：所有和 $S$ 中的点有连边的点组成的集合。

Hall 定理：二分图一部中选出点集 $S$，$S$ 中的每个点都能匹配，当且仅当 $\mathrm{\forall }T\subseteq S,|T|\le |N(T)|$。

P3488 [POI 2009] LYZ-Ice Skates

可以建出二分图，让人连向所有他能穿的鞋子。

套用 Hall 定理，代表人的点集是 $S$，人能选到的鞋子的点集就是 $|N(S)|$。

进一步发现，连续的子区间更容易不合法，因为不合法的 $T$，选择的鞋子一定有重合的部分，如果没有重合的部分，这个不合法的 $T$ 可以拆分成多个 $T^{\prime }$。考虑 $|T|=2$ 的情况，因为选择的鞋子已经重合，选择这中间的所有人都不会增加鞋子数 $|N(T)|$，而会增加 $|T|$。

因此问题转化成判断是否 $\mathrm{\forall }l,r$，满足 $\sum _{i=l}^r{a}_i\le k(r-l+1+d)$，即 $\sum _{i=l}^r(a_i-k)\le dk$，使用线段树维护最大子段和判断是否合法即可。