首先发现二分答案,然后问题就变成了一个二分图是否有完美匹配的问题,我们自然是希望用 Hall 定理来解决这一问题。
Hall 定理原本的描述还是太吃操作了,考虑猜结论,就是 \(a\) 排序后每个子区间对于其来说都合法那么我们就认为 Hall 定理是合法的,事实证明这是对的。
考虑将式子拆成贡献在两个点上的形式,扫描线即可解决问题,不过拆环为链会比较烦。
首先发现二分答案,然后问题就变成了一个二分图是否有完美匹配的问题,我们自然是希望用 Hall 定理来解决这一问题。
Hall 定理原本的描述还是太吃操作了,考虑猜结论,就是 \(a\) 排序后每个子区间对于其来说都合法那么我们就认为 Hall 定理是合法的,事实证明这是对的。
考虑将式子拆成贡献在两个点上的形式,扫描线即可解决问题,不过拆环为链会比较烦。