E2. Submedians (Hard Version)

在Codeforces上查看

问题描述

这是问题的困难版本。你需要找到所有次中位数，并为每一个找到对应的任意一个子数组。

定义

一个整数 $v$ 是一个长度为 $m$ 的数组 $b$ 的中位数，当且仅当：

• $v$ 大于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素，并且
• $v$ 小于或等于数组中至少 $\lceil \frac{m}{2} \rceil$ 个元素。

示例

• $[9, 3, 7]$ 的唯一中位数是 $7$。
• $[5, 3, 7, 9]$ 的中位数是 $5$、$6$ 和 $7$。
• $[2, 2, 2]$ 的唯一中位数是 $2$。

任务

给定一个整数 $k$ 和一个由 $1$ 到 $n$ 之间的整数组成的数组 $a_1, \ldots, a_n$。

一个从 $1$ 到 $n$ 的整数 $v$ 被称为次中位数，如果存在至少一对索引 $(l, r)$ 使得：

• $1 \leq l \leq r \leq n$
• $r - l + 1 \geq k$
• $v$ 是子数组 $[a_l, \ldots, a_r]$ 的一个中位数

找到所有次中位数，并为每一个找到对应的任意一对索引 $(l, r)$。

输入

每个测试包含多个测试用例。 第一行是测试用例的数量 $t$ ($1 \leq t \leq 50\,000$)。 接下来是测试用例的描述。

• 每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \leq k \leq n \leq 300\,000$)。
• 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$)。

保证所有测试用例的 $n$ 的总和不超过 $300\,000$。

输出

对于每个测试用例，按以下格式输出你的答案：

• 第一行输出 $c$，即次中位数的数量。
• 在接下来的 $c$ 行的第 $i$ 行，输出三个整数 $v_i$、$l_i$ 和 $r_i$，使得 $r_i - l_i + 1 \geq k$ 并且 $v_i$ 是子数组 $[a_{l_i}, \ldots, a_{r_i}]$ 的一个中位数。

每个次中位数应该只报告一次，即整数 $v_1, \ldots, v_c$ 必须是两两不同的。报告的顺序无关紧要。

如果存在多个解，你可以输出任意一个。

题解

这个问题的困难版本要求我们找到所有可能的次中位数。一个关键的洞察是，所有次中位数的集合构成一个连续的整数区间 [v_min, v_max]。如果我们能找到可能的最小次中位数 (v_min) 和最大次中位数 (v_max)，那么我们就可以证明任何满足 v_min <= v <= v_max 的整数 v 也是一个次中位数。

因此，总体策略是：

1. 找到最大次中位数 v_max 和一个对应的子数组 [l_max, r_max]。
2. 找到最小次中位数 v_min 和一个对应的子数组 [l_min, r_min]。
3. 为从 v_min 到 v_max 的每个整数生成一个有效的子数组。

寻找 v_max 和 v_min

寻找 v_max 的方法与问题的简单版本完全相同。我们可以对答案 x 进行二分搜索，使用谓词 check(x)：“是否存在一个子数组，其中大于等于 x 的元素数量至少等于小于 x 的元素数量？”。使这个条件为真的最大 x 就是 v_max。这可以在 $O(n \log n)$ 的时间内解决。

要找到 v_min，我们可以使用一个聪明的技巧。一组数 a 中的最小值与取反后的集合 -a 的最大值有关。具体来说，min(a) = -max(-a)。为了避免处理负数，我们可以使用一个大的常数 C，并说 v_min(a) = C - v_max(C - a)。我们可以将相同的 max_mid 函数应用于转换后的数组 a'_i = C - a_i 来找到 v_max(a')。然后，我们可以找到 v_min(a) = C - v_max(a')。这也需要 $O(n \log n)$ 的时间。

连续性论证

现在我们需要证明 v_min 和 v_max 之间的每个整数都是一个有效的次中位数。我们可以通过一个构造性的、“连续性”的论证来做到这一点。我们有一个中位数为 v_min 的子数组 [l_min, r_min] 和另一个中位数为 v_max 的子数组 [l_max, r_max]。

我们可以通过一系列单元素的变化将第一个子数组转换为第二个子数组。例如，我们可以将左边界 l_min 一次移动一步，直到它到达 l_max，然后对右边界也做同样的操作。当我们从一个子数组中添加或删除一个元素时，它的中位数值只能改变很小的量。因为变化是渐进的，我们的滑动窗口的中位数在转换过程中的某个点会经过 v_min 和 v_max 之间的每一个整数值。通过记录每一步的子数组，我们可以为该范围内的每个次中位数找到一个有效的窗口。

实现：滑动窗口中位数

为了高效地实现这个转换，我们需要一个能够维护滑动窗口中位数的数据结构。一个标准且高效的方法是使用两个平衡的多重集合（multiset）：

• 一个 low 多重集合，用于存储窗口中较小的一半元素。
• 一个 high 多重集合，用于存储较大的一半元素。

我们保持这两个集合的平衡，使它们的大小差异最多为一。有了这个结构，窗口的中位数总是在两个集合的“连接处”（具体来说，它将是 high 中的最小元素）。当一个元素被添加到窗口或从窗口中移除时，我们更新多重集合并重新平衡它们。这使我们能够在 $O(\log m)$ 的时间内找到新的中位数，其中 m 是窗口大小。

算法流程如下：

1. 用 v_min 子数组 [l_min, r_min] 的元素初始化两个多重集合。
2. 记录从 v_min 到初始窗口中位数的所有中位数。
3. 在一个循环中，应用单元素移动，将窗口从 [l_min, r_min] 滑动到 [l_max, r_max]。
4. 每次移动后，更新多重集合，找到新的中位数，并记录前一个中位数和新中位数之间的所有整数值，将它们与当前窗口关联起来。

这个过程为从 v_min 到 v_max 的每一个次中位数构造性地找到了一个有效的子数组，从而解决了问题。滑动窗口部分的复杂度与两个子数组之间的距离成正比，最多为 $O(n)$，每一步需要 $O(\log k)$，因此总复杂度由初始的 $O(n \log n)$ 搜索主导。

提交链接