← 返回题目列表

Codeforces · 1630/B

B. 范围和分区

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

给定一个包含 $$$n$$$ 整数的数组 $$$a$$$,找到一系列值 $$$[x, y]$$$ ($$$x \le y$$$),并将 $$$a$$$ 精确地拆分为 $$$k$$$ ($$$1 \le k \le n$$$) 子数组,方法如下:

- 每个子数组由 $$$a$$$ 的几个连续元素组成,即对于某些 $$$l$$$ 和 $$$r$$$ 来说,它等于 $$$a_l, a_{l+1}, \ldots, a_r$$$ ($$$1 \leq l \leq r \leq n$$$)。
- $$$a$$$ 中的每个元素都属于一个子数组。
- 在每个子数组中,$$$[x, y]$$$(含)范围内的元素数量严格大于该范围之外的元素数量。当且仅当 $$$x \le a_i \le y$$$ 时,索引为 $$$i$$$ 的元素位于 $$$[x, y]$$$ 范围内。

打印任何最小化 $$$y - x$$$ 的解决方案。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度以及分区中所需的子数组的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是数组的第 $$$i$$$ 元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

对于每个测试用例,打印 $$$k+1$$$ 行。

在第一行中,打印 $$$x$$$ 和 $$$y$$$ — 找到的范围的限制。

然后打印 $$$k$$$ 行,第 $$$i$$$ 行应包含 $$$l_i$$$ 和 $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — 第 $$$i$$$ 子数组的限制。

您可以按任意顺序打印子数组。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试中,应该只有一个子数组,它必须等于整个数组。 $$$[1, 2]$$$范围内有$$$2$$$元素,外部有$$$0$$$元素,如果选择的范围是$$$[1, 1]$$$,则内部($$$a_1$$$)内部存在$$$1$$$元素,外部($$$a_2$$$)内部存在$$$1$$$元素,则答案无效。

在第二个测试中,可以选择范围 $$$[2, 2]$$$,并将数组拆分为子数组 $$$(1, 3)$$$ 和 $$$(4, 4)$$$,在子数组 $$$(1, 3)$$$ 范围内有 $$$2$$$ 元素($$$a_2$$$ 和$$$a_3$$$) 和 $$$1$$$ 元素在 ($$$a_1$$$) 之外,子数组 $$$(4, 4)$$$ 中只有 $$$1$$$ 元素 ($$$a_4$$$),并且它在范围内。

在第三个测试中,可以选择范围 $$$[5, 5]$$$,并将数组拆分为子数组 $$$(1, 4)$$$、$$$(5, 7)$$$ 和 $$$(8, 11)$$$,在子数组 $$$(1, 4)$$$ 范围内有 $$$3$$$ 元素,并且$$$1$$$ 元素在外面,子数组 $$$(5, 7)$$$ 里面有 $$$2$$$ 元素,外面有 $$$1$$$ 元素,子数组 $$$(8, 11)$$$ 里面有 $$$3$$$ 元素,外面有 $$$1$$$ 元素。