P4518 [JSOI2018]绝地反击

约瑟夫用脑玩 · 2022-03-31 19:38:00 · 题解

主要来写 Hall 定理的部分，因为前面的部分想不到但大家都是一样的做法，后面的部分却是复杂度出现较大差异的地方。

感觉这个区间连边的二分图以前见过，比较经典，当做是复习 Hall 定理了。

首先答案有明显的可二分性，我们在 Um_Nik 的领导下先二分时间 t 使得每个飞机都到位。

那么一架飞机能走到范围的是一个圆，考虑能走到攻击轨道的哪些位置，即求交，显然发现是一段圆弧。

然后比较神的一步是调整，如果每个飞机都不在自己能到攻击轨道的圆弧的端点上，此时我们将整体向左向右移都是没问题的。

一定可以进行移动调整到某个飞机恰落在自己能到攻击轨道的圆弧的端点上，这样只要提前 O(n) 枚举了一个固定的飞船到一个固定的端点（就只有它所对应圆弧的两端）。

接下来 n 个位置就固定了，而非完全无法考虑的无限个位置，到了这一步有一些暴力的出路：

• 暴力连 n^2 条边，根据 Dinic 二分图是 M\sqrt N，复杂度为 O(n^3\sqrt n\log)。
• 精细实现版线段树优化隐式建边跑 Dinic，据笔者考虑可以做到 O(n^2\sqrt n\log^2) 的复杂度，这个复杂度是不优雅的算法中看上去最能过的了。
• 对于枚举一个固定的飞船到一个固定的端点时，顺次切换最近的飞船到固定端点，总切换次数未知且复杂度未知，没有分析比较玄学。（感觉复杂度比暴力还差，但有题解说这是 O(n^3\log) 的

不管怎么说，上述算法都不够优雅，稍微形式化的叙述一下我们要求的东西：

给你一个二分图，保证左部点向右部点连的边形成一个区间，判断是否有完美匹配。

说到完美匹配这种东西就应该想到 Hall 定理，再加上这道题的边很有特点。

首先考虑枚举哪部点的子集，尝试了一下右部点发现搞不动，于是我们先枚举一个左部点的一个子集看邻集。

最基本的 Hall 定理的逆否命题有：若无完美匹配，此判定与 \exists S,|S|>|N(S)| 充要，其中 N(S) 为左部点集 S 的子集。

由于邻集是一些区间的并且每个点只会连一个区间，比较经典的有将每个不交的邻集区间单独拎出来，分开考虑这些邻集的左部点邻集，有结论和原判定充要。

首先充分性显然，因为区间并是包含了只有一个区间的情况。

考虑必要性，去掉 |S|\le N(S) 的邻集区间，剩下的区间至少有一个 |S|>|N(S)|。

考虑固定邻集并贪心的往左部点集加点尽量使得 |S|>|N(S)|，如果一个左部点连的区间完全在邻集内部，将这个点并入我们考虑的子集显然更优。

否则是无法并入子集的，也就是这个贪心条件都是充要的，我们直接贪心选完后判定即可。

于是我们得到了一个不如暴力网络流的 O(n^4\log) 算法，如果固定邻集区间的右端点依次移动左端点并加入左部点就可以轻松做到 O(n^3\log)。

我们还可以更进一步，考虑依次移动右端点，并用线段树继承左端点的情况，相当于支持插入左部点对 |S| 产生一个区间的贡献，并支持查询区间最小值或最大值，看你维护 |S|-|N(S)| 还是 |N(S)|-|S|。

最后复杂度 O(n^2\log^2)，由于口胡不会求圆弧所以没有代码。

Upd：更新了一个不优雅算法的复杂度，笔者认为此题是有两种复杂度正确的算法的，但不优雅的算法非本题主要实现方式就不细讲了，可以参见。