← 返回题目列表

Codeforces · 1341/B

B. 纳斯蒂亚和门

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

2 月 14 日,丹尼斯决定把情人节礼物送给娜斯蒂亚,但除了在长度为 $$$k$$$ ($$$k \ge 3$$$) 的门上画一颗巨大的红心之外,没有想到更好的办法。娜斯佳对这份礼物感到非常困惑,所以她决定打破门,把它扔到山上。

山脉由一系列高度 $$$a_1, a_2, \dots, a_n$$$ 描述,从左到右 ($$$k \le n$$$)。保证相邻高度彼此不相等(即 $$$a_i \ne a_{i+1}$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$)。

段 $$$[l,r]$$$ 上的山峰(从 $$$l$$$ 到 $$$r$$$)称为索引 $$$i$$$,使得 $$$l < i < r$$$、$$$a_{i - 1} < a_i$$$ 和 $$$a_i > a_{i + 1}$$$。值得注意的是,该段的边界索引 $$$l$$$ 和 $$$r$$$ 不是峰值。例如,如果 $$$n=8$$$ 和 $$$a=[3,1,4,1,5,9,2,6]$$$,则段 $$$[1,8]$$$ 只有两个峰值(索引为 $$$3$$$ 和 $$$6$$$),并且段 $$$[3, 6]$$$ 上没有峰值。

为了打破门,Nastya 将门扔到一段 $$$[l,l+k-1]$$$ 的连续山脉,长度为 $$$k$$$ ($$$1 \le l \le n-k+1$$$)。当门接触到山峰时,它会分成两部分,之后这些部分会继续掉落成不同的两半,并且在接触到山峰时也会碎成碎片,以此类推。形式上,门将闯入的部分数量等于 $$$p+1$$$,其中 $$$p$$$ 是段 $$$[l,l+k-1]$$$ 上的峰值数量。

Nastya 想把它分成尽可能多的碎片。帮助她选择一段山$$$[l, l+k-1]$$$,使其上的山峰数量最多。如果存在多个最佳分段,Nastya 希望找到 $$$l$$$ 值最小的一个分段。

正式来说,您需要选择一段山峰 $$$[l, l+k-1]$$$ 具有最大数量的山峰。在所有这些段中,您需要找到具有最小可能值 $$$l$$$ 的段。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \leq k \leq n \leq 2 \cdot 10^5$$$) — 山的数量和门的长度。

输入数据集的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10 ^ 9$$$, $$$a_i \neq a_{i + 1}$$$) — 山脉的高度。

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

输出

对于每个测试用例,输出两个整数 $$$t$$$ 和 $$$l$$$ — 门可以分割成的最大部分数,以及门应重置为 $$$k$$$ 长度的段的左边界。

示例

输入 #1

5
8 6
1 2 4 1 2 4 1 2
5 3
3 2 3 2 1
10 4
4 3 4 3 2 3 2 1 0 1
15 7
3 7 4 8 2 3 4 5 21 2 3 4 2 1 3
7 5
1 2 3 4 5 6 1

输出 #1

3 2
2 2
2 1
3 1
2 3

注意

在第一个示例中,您需要选择从 $$$2$$$ 到 $$$7$$$ 的一段山脉。在该段中,索引 $$$3$$$ 和 $$$6$$$ 是峰值,因此答案是 $$$3$$$ (只有 $$$2$$$ 峰值,因此门将分成 $$$3$$$ 部分)。不难看出,$$$[1, 6]$$$ 和 $$$[3, 8]$$$ 山段不适合,因为它们只有 $$$1$$$ 峰值(对于第一段,$$$6$$$ 索引不是峰值,对于第二段,$$$3$$$ 索引不是峰值)。

在第二个示例中,您需要选择从 $$$2$$$ 到 $$$4$$$ 的一段山脉。在这个段中,索引$$$3$$$是一个峰值,所以答案是$$$2$$$(只有$$$1$$$峰值,所以门会分成$$$2$$$部分)。

在第三个示例中,您需要选择从 $$$1$$$ 到 $$$4$$$ 的一段山脉。在这个段中,索引$$$3$$$是一个峰值,所以答案是$$$2$$$(只有$$$1$$$峰值,所以门会分成$$$2$$$部分)。您可以看到,在线段 $$$[2, 5]$$$、$$$[4, 7]$$$ 和 $$$[5, 8]$$$ 上,峰值数量也是 $$$1$$$,但这些线段的左边框大于线段 $$$[1, 4]$$$,因此它们不是正确答案。