← 返回题目列表

Codeforces · 1637/B

B. MEX 和数组

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

设一个数组 $$$b_1, b_2, \ldots, b_k$$$。将该数组划分为段 $$$[l_1; r_1],[l_2; r_2],\l_c; r_c]$$$,其中 $$$l_1 = 1$$$,$$$r_c = k$$$,并且对于任何 $$$2 \leq i \leq c$$$ 都成立 $$$r_{i-1} + 1 = l_i$$$。换句话说,数组的每个元素都属于一个段。

让我们将分区的成本定义为 $$$$$$c + \sum_{i = 1}^{c} \operatorname{mex}(\{b_{l_i}, b_{l_i + 1}, \ldots, b_{r_i}\}),$$$$$$ 其中 $$$\operatorname{mex}$$$ 是一组数字$$$S$$$ 是集合 $$$S$$$ 中不出现的最小非负整数。换句话说,分区的成本是段的数量加上所有段的 MEX 之和。让我们将数组 $$$b_1, b_2, \ldots, b_k$$$ 的值定义为该数组所有分区的最大可能成本。

给定一个数组 $$$a$$$,大小为 $$$n$$$。求其所有子段的值之和。

数组 $$$x$$$ 是数组 $$$y$$$ 的子段,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$y$$$ 获得。

输入

输入包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 30$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 数组的长度。

第二行包含整数序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 数组元素。

保证所有测试用例的$$$n$$$ 值之和不超过$$$100$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

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

输出 #1

4
14
26
48

注意

在第二个测试用例中:

- 子段 $$$[2, 0, 1]$$$ 的最佳分区:$$$[2], [0, 1]$$$。该分区的成本等于 $$$2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0, 1\}) = 2 + 0 + 2 = 4$$$。
- 子段 $$$[2, 0]$$$ 的最佳分区:$$$[2], [0]$$$。该分区的成本等于 $$$2 + \operatorname{mex}(\{2\}) + \operatorname{mex}(\{0\}) = 2 + 0 + 1 = 3$$$
- 子段 $$$[2]$$$ 的最佳分区:$$$[2]$$$。该分区的成本等于 $$$1 + \operatorname{mex}(\{2\}) = 1 + 0 = 1$$$。
- 子段 $$$[0, 1]$$$ 的最佳分区:$$$[0, 1]$$$。该分区的成本等于 $$$1 + \operatorname{mex}(\{0, 1\}) = 1 + 2 = 3$$$。
- 子段 $$$[0]$$$ 的最佳分区:$$$[0]$$$。该分区的成本等于 $$$1 + \operatorname{mex}(\{0\}) = 1 + 1 = 2$$$。
- 子段 $$$[1]$$$ 的最佳分区:$$$[1]$$$。该分区的成本等于 $$$1 + \operatorname{mex}(\{1\}) = 1 + 0 = 1$$$。

所有子段的值总和等于 $$$4 + 3 + 1 + 3 + 2 + 1 = 14$$$。