ZOJ - 3872 Beauty of Array（子串的乘积的和）

Edward has an array <var>A</var> with <var>N</var> integers. He defines the beauty of an array as the summation of all distinct integers in the array. Now Edward wants to know the summation of the beauty of all contiguous subarray of the array <var>A</var>.

Input

There are multiple test cases. The first line of input contains an integer <var>T</var> indicating the number of test cases. For each test case:

The first line contains an integer <var>N</var> (1 <= <var>N</var> <= 100000), which indicates the size of the array. The next line contains <var>N</var> positive integers separated by spaces. Every integer is no larger than 1000000.

Output

For each case, print the answer in one line.

Sample Input

3
5
1 2 3 4 5
3
2 3 3
4
2 3 3 2

Sample Output

105
21
38

Source: The 12th Zhejiang Provincial Collegiate Programming Contest

             这道题就是~~所有的连续子序列中~~不重复的元素的和是多少：：

             这样~假设先不管求的是不重复元素~那我们该怎么算呢~请大家看下面那幅图

                （大家别介意~~~）假设四个元素分别是ABCD~~那么在只有第一个元素的时候所有子序列和是A；而在有两个元素的时候（AB）这样的话是A+AB+B，比原来多了AB和B的和~~以此类推~~这样在多了第k个元素的时候~总的序列和增加的就是（上一个序列和增加的+k*这个元素）~~；

                   这样的话如果是各个子序列（中的不同元素的和）的和呢：：我们假设B和D相等~~辣么在增加到D的时候~D的实际上增加的就只有（ABC  BC CD D）少了（2）个D的值~~那如果是A和D相等呢，那么增加的就是（ABC BCD CD D）少了（1）个D~~~所以不同元素和这个每次增加的数量和这个元素上一次出现的位置有关~~这样就好做了

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int last[100005];//记录各个数上次出现的位置
int main()
{
	int te;
	cin >> te;
	while (te--)
	{
		int n;
		memset(last, 0, sizeof(last));
		scanf("%d", &n);
		long long int ans = 0;
		long long int node = 0;。。每个节点增加的数值
		for (int s = 1; s <= n; s++)
		{
			int tem;
			scanf("%d", &tem);
			node+=(s - last[tem])*tem;
			ans += node;
			last[tem] = s;
		}
		cout << ans << endl;
	}
	return 0;
}