← 返回题目列表

Codeforces · 2053/H

H. 精致反单调的操作

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

生活中总是有很多重复的任务。艾丽丝总是不喜欢它们,所以她拒绝重复它们。然而,时光无法倒流;我们只需要继续前进。

形式上,Iris 有一个整数序列 $$$a_1, a_2, \ldots, a_n$$$,其中序列中的每个数字都在 $$$1$$$ 和 $$$w$$$ 之间(包含这两个数字)。保证 $$$w \geq 2$$$。

Iris 定义的操作是选择两个数字 $$$a_i, a_{i+1}$$$ 满足 $$$a_i = a_{i+1}$$$,然后将它们更改为 $$$[1, w]$$$ 范围内的两个任意整数。 Iris 不喜欢相等,因此她必须保证运算后 $$$a_i \neq a_{i+1}$$$ 。两个相同的对 $$$a_i, a_{i+1}$$$ 可以被选择多次。

Iris 想知道 $$$a$$$ 经过几次(可能是零)运算后所有元素的最大可能总和,以及达到该最大值所需的最少运算次数。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$w$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$2 \leq w \leq 10^8$$$) - 数组的长度和元素的最大允许值。

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

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出两个整数 - 分别是 $$$a$$$ 的所有元素的最大可能总和以及所需的最小操作数。

示例

输入 #1

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

输出 #1

15 0
34 6

注意

在第一个测试用例中,无法执行任何操作,因此答案分别为 $$$\sum a_i = 15$$$ 和 $$$0$$$。

在第二个测试用例中,可以执行如下操作:

$$$$$$[3, 1, 2, 3, 4, \underline{1, 1}] \rightarrow [3, 1, 2, 3, \underline{4, 4}, 5] \rightarrow [3, 1, 2, \underline{3, 3}, 5, 5] \rightarrow [3, 1, \underline{2, 2}, 5, 5, 5] \rightarrow [3, \underline{1, 1}, 5, 5, 5, 5] \rightarrow [\underline{3, 3}, 5, 5, 5, 5, 5] \rightarrow [4, 5, 5, 5, 5, 5, 5]$$$$$$

可以证明这是最优的,因此我们应该分别输出 $$$\sum a_i = 34$$$ 和操作数 $$$6$$$。