← 返回题目列表

Codeforces · 2128/E1

E1. 子中位数(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是,在这个版本中,您被要求仅找到最大的子数组 次中位数.

只有当问题的两个版本都得到解决时,你才可以进行黑客攻击。

整数 $$$v$$$ 是 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 当且仅当:

  • $$$v$$$ 大于或等于数组的至少 $$$\lceil \frac{m}{2} \rceil$$$ 元素,并且
  • $$$v$$$ 小于或等于数组的至少 $$$\lceil \frac{m}{2} \rceil$$$ 元素。
例如:
  • 唯一 $$$[9, 3, 7]$$$ 的 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 是 $$$7$$$,
  • 这 中位数 $$$[5, 3, 7, 9]$$$ 的 是 $$$5$$$、$$$6$$$ 和 $$$7$$$,并且 $$$[2, 2, 2]$$$ 的
  • 唯一 $$$[9, 3, 7]$$$ 的 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 是 $$$2$$$。

给定一个整数 $$$k$$$ 和一个 $$$a_1, \ldots, a_n$$$ 数组,其中整数介于 $$$1$$$ 和 $$$n$$$ 之间。

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

  • $$$1 \leq l \leq r \leq n$$$,
  • $$$r - l + 1 \geq k$$$,
  • $$$v$$$ 是 子数组 $$$[a_l, \ldots, a_r]$$$ 的 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 。

可以证明总是存在至少一个 次中位数。找到最大值 次中位数 $$$v_\max$$$ 和任何相应的索引对 $$$(l, r)$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 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$$$ 是其之一 中位数 $$$[5, 3, 7, 9]$$$ 的.

如果有很多解决方案,您可以打印其中任何一个。

示例

输入
复制

7
4 3
4 1 2 4
5 2
1 2 3 2 1
5 3
1 2 3 2 1
5 3
1 1 2 5 3
1 1
1
2 1
2 1
4 1
1 2 1 3

输出
复制

4 1 4
3 3 4
2 2 4
3 3 5
1 1 1
2 1 2
3 4 4

注意

在第一个测试用例中,长度至少 $$$k = 3$$$ 的子数组是

  • $$$(l = 1, r = 3)$$$: $$$[4, 1, 2]$$$ 唯一 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 是 $$$2$$$,
  • $$$(l = 2, r = 4)$$$: $$$[1, 2, 4]$$$ 唯一 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的 是 $$$2$$$,并且
  • $$$(l = 1, r = 4)$$$: $$$[4, 1, 2, 4]$$$ 其中 中位数 $$$[5, 3, 7, 9]$$$ 的 是 $$$2$$$、$$$3$$$ 和 $$$4$$$。

在第二个测试用例中,一个可能的输出是 $$$(l = 3, r = 4)$$$,其 中位数 $$$[5, 3, 7, 9]$$$ 的 是 $$$2$$$ 和 $$$3$$$。

请注意,可以证明长度至少为 $$$2$$$ 的子数组不承认 $$$4$$$ 或 $$$5$$$ 作为 中位数 长度为 $$$m$$$ 的数组 $$$b$$$ 的.