#P18320. Score Sum
Score Sum
Score Sum
设数组 的长度为 。下面定义它的得分函数。
令 表示子数组 中不同元素的数量,并定义
在所有满足 的数对中,先选择使 最大的数对。如果有多个,选择其中 最小的数对。如果仍有多个,可以任选一个。
最终定义 ,也就是先最大化 、再最小化长度后所得到的子数组长度。
单独求一个数组的得分太简单了,因此现在需要对所有子数组求和。给定数组 ,求
$$\sum_{L=1}^{N}\sum_{R=L}^{N}\operatorname{score}(A[L,R]),$$其中 表示子数组 。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例包含两行:
- 第一行包含整数 ,表示数组长度。
- 第二行包含 个整数 。
输出格式
对于每个测试用例,输出一行,包含所有子数组得分之和。
数据范围
- ;
- ;
- ;
- 全部测试用例的 之和不超过 。
样例
输入
4
2
1 1
3
1 3 1
5
1 3 1 2 3
7
1 2 3 1 5 3 1
输出
4
8
26
62
说明
第一个测试用例共有三个子数组:两个不同位置上的 ,以及一个 。
- 对于 ,只有一个可选区间,所以得分为1。
- 对于 ,只有整个长度2的区间能够取得最大的 值,所以得分为2。
因此答案是 。