Distinct Values Sum

题目描述

给定一个数组 x_1,x_2,$\dots$,x_n。令 d(a,b) 表示子数组 x_a,x_{a+1},$\dots$,x_b 中不同值的个数。 你的任务是计算和 $\sum_{a=1}^n \sum_{b=a}^n d(a,b)$，即对所有子数组的 d(a,b) 求和。

输入格式

第一行是一个整数 n：数组长度。 下一行有 n 个整数 x_1,x_2,$\dots$,x_n：数组的元素。

输出格式

输出一个整数：所求的和。

5
1 2 3 1 1

29

提示

$1 \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$ 样例解释：在这个数组中，有 6 个子数组有 1 个不同值，4 个子数组有 2 个不同值，5 个子数组有 3 个不同值。因此，和为 6\cdot1+4\cdot2+5\cdot3=29。

标签: CSES3150|附加题1

来源

CSES3150|附加题1