CF2128E1 Submedians (Easy Version)

这是该问题的简单版本。唯一的区别在于，在本版本中，你只需要找到最大子中位数对应的一个子数组。 只有在两个版本都被解决的情况下，你才能进行 hack。 对于长度为 $m$ 的数组 $b$，整数 $v$ 是 $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$。 如果存在至少一对下标 $(l, r)$ 满足： - $1 \leq l \leq r \leq n$， - $r - l + 1 \geq k$， - $v$ 是子数组 $[a_l, \ldots, a_r]$ 的中位数， 则称 $1$ 到 $n$ 之间的整数 $v$ 是一个子中位数。 可以证明，至少存在一个子中位数。请你找出最大的子中位数 $v_{\max}$，以及任意一组对应的下标对 $(l, r)$。

每组测试数据包含多组测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 50000$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 300000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。 保证所有测试用例中 $n$ 的总和不超过 $300000$。

对于每组测试用例，输出三个整数 $v_{\max}$、$l$ 和 $r$，表示最大子中位数 $v_{\max}$ 以及一个长度不少于 $k$ 的子数组的区间 $[l, r]$（$r - l + 1 \geq k$），使得 $v_{\max}$ 是该子数组的中位数之一。 如果有多组解，输出任意一组均可。

在第一个测试用例中，长度至少为 $k = 3$ 的子数组有： - $(l = 1, r = 3)$：$[4, 1, 2]$，唯一的中位数是 $2$， - $(l = 2, r = 4)$：$[1, 2, 4]$，唯一的中位数是 $2$， - $(l = 1, r = 4)$：$[4, 1, 2, 4]$，中位数是 $2$、$3$ 和 $4$。 在第二个测试用例中，一种可能的输出是 $(l = 3, r = 4)$，其中中位数是 $2$ 和 $3$。 注意，可以证明长度至少为 $2$ 的任何子数组都不可能有 $4$ 或 $5$ 作为中位数。 由 ChatGPT 4.1 翻译