Q6.4.6.2. 配对1 题解

发布时间 2023-11-16 16:20:12作者: include_c

原题链接

\(b\) 的顺序与答案无关,先排序。能与 \(a_i\) 配对的肯定是 \(b\) 的末尾一段,因为 \(a_i+b_j\ge h\),那么一定有 \(a_i+b_{j+1}\ge h\)

\(c_i\) 为与 \(b_i\) 配对的 \(a\) 的个数,显然 \(c\) 是单调不下降的。

如果任意都有 \(c_i\ge i\),这说明当前的 \(a\) 是与 \(b\) 匹配的!(霍尔定理),于是我们可以先把 \(c_i\) 减去 \(i\),枚举每个 \(a\) 的长度为 \(m\) 连续子序列的结尾,用线段树维护 \(c\),如果全局最小值 \(\ge0\),说明匹配,答案 \(+1\)