H题 | 权值计算

解题思路：

我们观察题目给出的伪代码，发现任意一个子数组 () 的权值，是其每个前缀数组的数字种类数之和。

对于子数组 1 2 3 2，所有前缀及对应种类数为： 1 => 种数字

1 2 => 种数字

1 2 3 => 种数字

1 2 3 2 => 种数字

则子数组 1 2 3 2 的权值为 。

题目要求的是所有非空子数组的权值之和，不妨将问题转化，我们发现权值本质上是由数组的每个位置贡献出来的，那么单独求解每个位置的贡献，求和即可得到答案。

对于第 () 个数 ，要想对某个子数组 () 产生贡献，那么这个子数组必须包含它，即满足 。

那么， 对这个子数组的具体贡献是多少呢？如果 在该子数组中第一次出现，显然它会使后面所有位置的种类数比没有 时多 ，而对前面没有任何贡献。这些多出来的 就是 对子数组 的贡献。

我们固定 ，只看每个 ，我们发现这种种类数加 的操作一旦产生是无法消除的，也就是这个加 操作会从位置 一直执行到位置 。由于 的取值是 ()， 对每个区间的贡献依次为 ，其中 为 的长度，即 。那么总贡献就是 ，根据等差数列求和公式，也可以写成 。

我们再看不同的 对 贡献的影响，已知 ，依次从右往左枚举 ，每次枚举都会引入左侧新的元素。

当引入的元素和 不同时， 的贡献依然满足上述公式 ，因为引入的所有元素都在 前面，而上面说过 对前面没有任何贡献；

而当引入的元素和 相同时， 将不再产生任何贡献，因为前面的与 相同的元素已经提前干了 干的所有活了。

总结一下，当 不是第一次出现时，它的贡献为 ；否则它的贡献在 确定时为 。那么能使 第一次出现的 一共有多少种取值呢？显然 只能取到 左侧第一个与 相同的元素之后。

我们计 为 上次出现的位置，从左往右遍历数组并更新 ，符合条件的 一共有 个。而 对每个符合条件的 都有 的贡献，因此 产生的总贡献为 。

示例代码：

void solve() {
	unordered_map<int, int>lst;
	int n, x, ans = 0;
	cin >> n;

	for (int i = 1; i <= n; ++i) {
		cin >> x;
		int cnt = i - lst[x], len = n - i + 1;
		ans += cnt * len * (len + 1) / 2;
		lst[x] = i;
	}

	cout << ans << '\n';
}