题解 | H

题目 输入 输出

思路

要算权值需要先理解f函数，f函数计算的是，数组中未重复数的前项个数的累加和。

如{1 3 1}，通过f算出来是1+2+2=5；

题目要求数组所有非空子数组的权值之和，即{1}，{3}，{1}，{1，3}，{3，1}，{1，3，1}权值和。

为了避免超时要用到贡献法。

贡献法

对于1 3 1 最后答案是14；

其中第一个1提供了6（{1}....1;{1,3,1}....3;{1,3}....2;）;

而3提供了6（{1，3，1}....2;{3}....1;{1,3}....2;{3,1}....2）;

第二个1提供了2（{1}....1;{1,3,1}.....0;{1,3}....0;{3,1}...1）;

为什么两个1的贡献不相同？

对于{1，3，1}数组，进入f函数最后返回的数是5，而这个5是由1+2+2构成的；

第二个1进入f函数时对current——count没有影响，继而对答案没有影响，所以贡献是0；

而第一个1，对答案影响了3次，所以贡献是3.

最后答案怎么算

单个元素（前面没有重复）对答案的影响是（自身下标后面长度（后面长度-1）/2）；

（有重复）（（自身下标-上一个重复元素下标）后面长度（后面长度-1）/2）；

每一项贡献加起来就是答案。

完整代码

```#include<bits/stdc++.h>
using namespace std;
int a[100005];

unordered_map<int,int> m;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        long long ans=0;
        for(int i=1;i<=n;i++){
            long long ch=n-i+1;
            if(m.count(a[i])==0){
                ans+=i*ch*(ch+1)/2;
                m[a[i]]=i;
            }
            else{
                ans+=(i-m[a[i]])*ch*(ch+1)/2;
                m[a[i]]=i;
                
            }
        }
        cout<<ans<<endl;
        m.clear();
    }
    return 0;
}