【题解】CF1949B | 二分答案 霍尔定理

本题可以做到低于 \(O(n^2)\)。

最大化最小值，考虑二分答案 \(v\) 变为检查可行性：每个主菜匹配的开胃菜的两个值都要在 \((-\infty,x-v],[x+v,+\infty]\) 间选取，问是否存在主菜与开胃菜的完美匹配。

对开胃菜排序，得到第 \(i\) 个主菜可以匹配到的开胃菜集合为一个后缀和一个前缀：\([1,L_i]\cup [R_i,n]\)。

做法一

考虑使用霍尔定理检查完美匹配：枚举 \(S\) 并检查 \(|f(S)|-|S|\) 的最小值是否为 \(0\)，其中 \(f(S)\) 表示与左部点 \(S\) 存在连边的右部点集合。

枚举 \(S\) 是困难的，\(S\) 总共有 \(2^n\) 种，不妨枚举 \(f(S)\)，并考虑最大的 \(|S|\)，首先 \(f(S)\) 一定是若干前缀和后缀的并，所以 \(f(S)\) 的形态为 \([1,l]\cup [r,n]\)。

枚举 \(l\)，\(r\)，对于一个 \(f(S)=[1,l]\cup [r,n]\) 最大的 \(|S|\) 即 所有点 \(u\) 满足存在连边的右部点 \(e(u)\in f(S)\) 的 \(u\) 构成的集合，即 \(\sum[L_i\leq l\land R_i\geq r]\)，直接做可以 \(O(n^2\log a)\)。

使用线段树在扫描 \(l\) 时维护 \(r\) 的答案，支持区间加区间最值，容易做到 \(O(n\log n\log a)\)。

做法二，还能再快一点。

该问题弱于 AGC076F，使用反悔贪心即可。时间复杂度 \(O(n\log n\log a)\)，注意到每个点不能匹配的区间是单调的，所有优先队列可以换成队列，时间复杂度 \(O(n\log a)\)。