E1. Submedians (Easy Version)

在Codeforces上查看

问题描述

这是问题的简单版本。唯一的区别是，在这个版本中，你只需要为最大次中位数找到一个子数组。

只有在解决了两个版本的问题后，你才能进行hacks。

定义

一个整数 $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]$ 的一个中位数

可以证明，总存在至少一个次中位数。找到最大次中位数 $v_{max}$ 和任意对应的索引对 $(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$。

输出

对于每个测试用例，输出三个整数 $v_{max}$、$l$ 和 $r$ — 最大次中位数 $v_{max}$ 和一个长度至少为 $k$ ($r - l + 1 \geq k$) 的子数组的边界，使得 $v_{max}$ 是其一个中位数。

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

题解

问题要求找到最大次中位数 v_max。这种结构表明我们可以对答案进行二分搜索。我们需要找到一个单调的谓词 check(x) 来指导二分搜索。

让我们定义 check(x) 为：“是否存在一个长度为 m = r-l+1 >= k 的子数组 a[l...r]，使得其中大于或等于 x 的元素数量至少等于小于 x 的元素数量？”。

二分搜索将找到使 check(v_ans) 为真的最大整数 v_ans。我们将证明这个 v_ans 就是最大次中位数。

check(x) 函数

为了高效地实现 check(x)，我们将数组 a 转换为一个辅助数组 b：

• 如果 a[i] >= x，则 b[i] = 1
• 如果 a[i] < x，则 b[i] = -1

子数组 a[l...r] 中“大于等于 x 的元素数量 >= 小于 x 的元素数量”的条件等价于 b 中对应元素的和为非负：sum(b[l...r]) >= 0。

我们可以使用前缀和在 $O(n)$ 时间内找到是否存在这样的子数组。设 P 是 b 的前缀和数组（P[i] = sum(b[1...i])）。我们需要找到满足 r-l+1 >= k 的 l, r，使得 P[r] - P[l-1] >= 0，即 P[r] >= P[l-1]。

对于从 k 到 n 的每个 r，我们检查 P[r] >= min(P[0], P[1], ..., P[r-k]) 是否成立。这个检查可以通过从 k 到 n 遍历 r，同时维护所需窗口内的最小前缀和来完成。

正确性证明

设 v_ans 是我们二分搜索返回的值。我们需要证明 v_ans 是真正的最大次中位数 v_max。

1. v_max <= v_ans：设 v_max 是真正的最大次中位数。根据定义，存在一个长度为 m 的子数组 A'，其中心位数是 v_max。为了让 v_max 成为 A' 的中位数，大于等于 v_max 的元素数量必须至少为 $\lceil m/2 \rceil$。这意味着大于等于 v_max 的元素数量至少等于小于 v_max 的元素数量。因此，check(v_max) 为真。由于我们的二分搜索找到了使 check 为真的最大值 v_ans，我们必须有 v_ans >= v_max。

2. v_ans <= v_max：这需要证明 v_ans 是一个次中位数。根据我们二分搜索的定义，check(v_ans) 为真，而 check(v_ans + 1) 为假。 由于 check(v_ans) 为真，存在一个长度为 m 的子数组 A'，其中：

   • p = count(a_i >= v_ans)
   • q = count(a_i < v_ans)
   • p >= q

   我们需要证明 v_ans 是这个子数组 A' 的一个中位数。中位数的定义需要两个条件： a) count(a_i >= v_ans) >= \lceil m/2 \rceil：即 p >= \lceil m/2 \rceil。由于 p >= q 且 p+q=m，这个条件总是成立的。 b) count(a_i <= v_ans) >= \lceil m/2 \rceil：这是我们需要证明的。设 p_eq 是等于 v_ans 的元素数量。条件是 q + p_eq >= \lceil m/2 \rceil。

   我们利用 check(v_ans + 1) 为假这一事实。对于我们特定的子数组 A'，这意味着大于等于 v_ans + 1 的元素数量小于小于 v_ans + 1 的元素数量。

   • count(a_i >= v_ans + 1) 是 p - p_eq。
   • count(a_i < v_ans + 1) 是 q + p_eq。
   • 所以，我们有不等式：p - p_eq < q + 2*p_eq，简化为 p < q + 2*p_eq。

   我们用反证法，假设我们的条件(b)是假的：q + p_eq < \lceil m/2 \rceil。 这意味着 q + p_eq <= \lceil m/2 \rceil - 1。 由于 m = p+q，我们有 p = m-q。将此代入从 check(v_ans+1) 得到的不等式中： m - q < q + 2*p_eq \implies m < 2q + 2*p_eq \implies m/2 < q + p_eq。 结合我们的假设和这个结果，我们得到： m/2 < q + p_eq \le \lceil m/2 \rceil - 1。 这个不等式对于任何整数 m 都不可能成立。例如，如果 m=2k，它变成 k < q+p_eq \le k-1，这是一个矛盾。如果 m=2k+1，它变成 k+0.5 < q+p_eq \le k，也是一个矛盾。 因此，我们的假设必定是错误的。条件(b) q + p_eq >= \lceil m/2 \rceil 必须为真。

   由于两个中位数条件对于子数组 A' 中的 v_ans 都成立，所以 v_ans 是一个次中位数。这意味着 v_ans <= v_max。

结合两个部分，我们得出 v_ans = v_max。该算法是正确的。

提交链接