CF1527C Sequence Pair Weight

一个序列的权值被定义为具有相同值的无序下标对 $(i, j)$（其中 $i < j$）的数量（即 $a_i = a_j$）。例如，序列 $a = [1, 1, 2, 2, 1]$ 的权值为 $4$。具有相同值的无序下标对为 $(1, 2)$、$(1, 5)$、$(2, 5)$ 和 $(3, 4)$。 给定一个长度为 $n$ 的整数序列 $a$。请输出 $a$ 的所有子段的权值之和。 如果序列 $b$ 可以通过从序列 $a$ 的开头删除若干（可能为零或全部）元素，并从结尾删除若干（可能为零或全部）元素得到，则称 $b$ 是 $a$ 的一个子段。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示该序列所有子段的权值之和。

- 在第 1 个测试用例中，序列 $[1, 2, 1, 1]$ 所有长度大于 $1$ 的子段为： 1. $[1, 2]$，有 $0$ 个有效无序对； 2. $[2, 1]$，有 $0$ 个有效无序对； 3. $[1, 1]$，有 $1$ 个有效无序对； 4. $[1, 2, 1]$，有 $1$ 个有效无序对； 5. $[2, 1, 1]$，有 $1$ 个有效无序对； 6. $[1, 2, 1, 1]$，有 $3$ 个有效无序对。 答案为 $6$。 - 在第 2 个测试用例中，序列所有元素均不相同，因此任意子段都没有相同值的无序对。答案为 $0$。 由 ChatGPT 4.1 翻译