声明：本题解有参考验题人题解

题目描述

Algorithm 1 函数 f 用于计算数组 s 的权值
function f(l, r, s)
distinct ← ∅
total ← 0
current_count ← 0
for i ← l to r do
  if s[i] ∉ distinct then
current_count ← current_count + 1
distinct ← distinct ∪ {s[i]}
end if
total ← total + current_count
end for
return total
end function

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

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

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≤T≤10 ^ 4 )，代表数据组数，每组测试数据描述如下：

第一行输入一个整数 𝑛 ( 1 ≤ 𝑛 ≤ 1 0 ^ 5 ) ，表示数组长度。 第二行输入 n 个整数 𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 ( 1 ≤ 𝑎 𝑖 ≤ 1 0 ^ 9 ) ，表示数组中的元素。

除此之外，保证单个测试文件的 n 之和不超过 1 0 ^ 5 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所有子数组的权值之和。 伪代码大致意思是说计算下标l到l,l到l+1,l到l+2,......,l到r区间内每个区间数组s有多少个不同的数字,我们需要按顺序记录每个数字出现的各个位置，这里我们用mp[num][i]来表示第i（i>0)个表示数字num的数的位置， 以便后续计算，注意对于每一个数的位置中先插入一个0，方便计算，下面用示例1的一组数据举例：

3

1 3 1

这组数据的非空子数组有{1},{3},{1},{1,3},{3,1},{1,3,1},前三个无需多言贡献都为1，{1，3}的贡献为看第一个位置有一个不相同的数1，第二个位置有两个不相同的数1和3，故贡献为3，{3，1}看第一个位置有一个不相同的数3，第二个位置有两个不相同的数3和1，贡献同样为3，{1，3，1}第一个不相同的数1，第二个位置有两个不相同的数1和3，第三个位置有两个不相同的数1和3，贡献为5，相加得贡献为1+1+1+3+3+5=14. 我们不妨计算以每个数可以为总贡献贡献多少，让我们来看第二组样例：

6

1 1 4 5 1 4

拿第一个4对于总贡献的贡献举例，有{1，1，4}，{1，1，4，5}，{1，1，4，5，1}三个子数列中4的贡献(n-i+1)(n-i+2)/2，以及{1，4}，{1，4，5}，{1，4，5，1}的(n-i+1)(n-i+2)/2点贡献和{4}，{4，5}，{4，5，1}的(n-i+1)(n-i+2)/2点贡献，故第一个4的贡献可以视作(n-i+1)(n-i+2)/2*(mp[1][i+1]-mp[1][i])，mp[1][i+1]-mp[1][i]为同一个数字两位置的差值。 代码如下：

void solve()
{
	ll n,sum=0;
	cin>>n;
	map<ll,vector<ll>>mp;
	for(ll i=1;i<=n;i++)
	{
		ll num;
		cin>>num;
		if(mp.count(num)==0)
			mp[num].push_back(0);
		mp[num].push_back(i);
	}
	for(auto &[key,val]:mp)
	{
		for(ll i=0;i<(ll)val.size()-1;i++)
		{
			ll l=n-val[i+1]+1;
			sum+=l*(l+1)/2*(val[i+1]-val[i]);
		}
	}
	cout<<sum<<endl;
}

如有错误，烦请指正谢谢