[OOI 2024] Almost Certainly

· · 题解

这是官方题解的 AI 中文翻译。

子任务 1.

对于每一个前缀，枚举所有将要被移除的数字对。之后，从数组中移除它们，并统计使两个数组相等所需的操作次数。操作次数等于第一个数组所有元素之和减去第二个数组所有元素之和。只有当对每个 i 都有 a_i \geq b_i 时，才能使它们相等。该解法的复杂度为 O(n^4)。

子任务 2.

我们对上一子任务的解法进行优化。我们希望每次从两个数组中各移除一个元素，使得它们之间的差值尽可能大。将两个前缀分别排序。注意到，如果我们可以移除 a_i 和 b_j，那么也可以移除 a_{i-1} 和 b_j，以及 a_i 和 b_{j+1}。因此，我们不需要枚举 O(n^2) 的所有移除对，而是可以枚举第一个数组中的元素，并通过指针移动在第二个数组中寻找对应元素。该解法的复杂度为 O(n^3)。

子任务 3.

我们进一步优化上一子任务的解法。我们需要更快地判断 a_i \geq b_i 是否成立。为此，需要注意，b_i 只会和 a_i 或 a_{i+1} 进行比较。而且，两个前缀都可以被划分为 O(1) 个区间，每个区间只需进行一种类型的比较。我们可以用前缀和预处理每种比较类型是否成立，这样就能在 O(1) 时间内完成正确性检查。该解法的复杂度为 O(n^2 \log n)。

完整解法的思路

我们将两个数组视为一组区间 [b_i, a_i]。注意，最终答案中 a_i < b_i 的情况一定不会更优。因此，最终答案的结构如下：移除所有 a_i = b_i 的下标。将剩下的数按 a_i 升序排序，此时有 a_1 \leq a_2 \leq \ldots \leq a_n 且 b_1 < a_1, b_2 < a_2, \ldots, b_n < a_n。此时，很容易发现需要移除 a_n 和 b_1。

那么，为了保证移除 a_n 和 b_1 后仍然合法，区间需要满足什么条件？即 b_2 \leq a_1, b_3 \leq a_2, \ldots, b_n \leq a_{n-1}。从区间的角度来看，这意味着这些区间都连成了一个连通块。此时，答案就是所有区间长度之和减去最长连通块的区间长度。

子任务 4-5.

由此可以看出，子任务 4 的答案为所有区间长度之和减去最长区间长度。对于第 5 组，需要维护当前的连通块，并在可能时扩展它，同时记下此前最长的连通块长度。

完整解法

在完整解法的实现中，我们维护当前的区间连通块。每次处理新前缀时，需要能够将与新区间相交的连通块合并。这些操作可以通过 std::set 容易地实现。该解法的时间复杂度为 O(n \log n)。