题目大意：

 1: function f(l, r, s)
 2:     distinct ← ∅
 3:     total ← 0
 4:     current_count ← 0
 5:     for i ← l to r do
 6:         if s[i] ∉ distinct then
 7:             current_count ← current_count + 1
 8:             distinct ← distinct ∪ {s[i]}
 9:         end if
10:         total ← total + current_count
11:     end for
12:     return total
13: end function

如上是一段计算数组权值的伪代码，通过调用 f(1,m,s) 计算一个长度为 m 的数组 s1,s2,..,sm的权值，现在 Bingbong 有一个长度为 n的数组 a1,a2,…,an请你帮助他求出所有非空子数组的权值之和。

【名词解释】 子数组：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。

解题思路： 根据伪代码我们可以得知题目要求我们求出一个数组的每个元素前缀里不同元素的个数和，求权值和。暴力必然会超时，故而使用这类题目的惯用套路：分别求每个元素的贡献值，最后加起来获得总值。

参考代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin>>t;
	for(int k=0;k<t;k++){
		ll n;
		cin>>n;
		vector<ll> a(n+1);
		map<int,int>mp;
		ll sum=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			sum+=(i-mp[a[i]])*((n-i+1)*(n-i+2)/2);
			//如果key未出现过，自动为这个key创建条目,并将对应的 value 初始化为
			//「该类型的默认值」，int 类型的默认值是 0.
> 			mp[a[i]]=i;
		}
		cout<<sum<<'\n';
	}
	return 0;
}

代码解释：

map<int,int>mp: 记录每个元素【上一次出现的位置】，初始为0（未出现过）；

sum+=(i-mp[a[i]])((n-i+1)(n-i+2)/2): 我们可以将这个公式拆成两部分来理解：

mp[a[i]]： 是元素上一次出现的位置（初位置为0），

i-mp[a[i]]： 是以a[i]为“新元素”的子数组左端点的数量（合法左端点）

(n-i+1)*(n-i+2)/2：是右端点贡献值，右端点贡献总和是a[i]对所有以它为“新出现元素”的子数组的右端点贡献和，是一个等差数列求和

最终sum+=每个元素的合法左端点数*右端点贡献和