7349. 不同数值和 (Distinct Values Sum)
时间限制：1000 MS 内存限制：512 MB
题目描述
给你一个数组 $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)$$ ### 输入格式 第一行包含一个整数 $n$，表示数组大小。 第二行包含 $n$ 个整数 $x\_1,x\_2,\dots,x\_n$，表示数组内容。 ### 输出格式 输出一个整数，表示要求的总和。 ### 输入输出样例 #### 输入 #1 ``` 5 1 2 3 1 1 ``` #### 输出 #1 ``` 29 ``` ### 说明/提示 #### 样例解释 在该数组中，有 $6$ 个子数组包含 $1$ 个不同数值，有 $4$ 个子数组包含 $2$ 个不同数值，有 $5$ 个子数组包含 $3$ 个不同数值。因此总和为 $6 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 29$。 #### 数据规模与约定 * $1 \le n \le 2 \cdot 10^5$ * $1 \le x\_i \le 10^9$