对于这道题,先解释一下一段数组的权值

从伪代码看,就是Σ_{i=l}^{r}dis(l,i),其中dis(l,i)代表s数组按下标(从一开始)从l到i多少个不同的元素,这就是一个数组的权值计算公式

但是,我们还需要计算所有子数组的权值,因此我们需要得到所有的子数组

最终答案也就是ans=Σ_{l=1}^{n} Σ_{r=l}^{n} Σ_{i=l}^{r} dis(l,i)

但是这个用到了三重循环,非常恐怖的复杂度,因此我们必须进行优化,至少要到n log n才行,但是这个可以优化到n

先看内层的两个循环,此时l看做常数,那么dis(l,i)就只与i有关了,对于某个dis(l,i),我们不难发现,当r从l加到n的过程中dis(l,i)是重复出现的,出现的次数和r有关,而dis(l,i)要想和r有关,就必须满足r大于等于i,也就是r从i加到n,一共n-i+1次(假设dis(l,3),当r等于1和2的时候肯定是没有dis(l,3)的)

那么内层的两个循环压成了Σ_{i=l}^{n} dis(l,i)* (n-i+1)

于是ans=Σ_{l=1}^{n} Σ{i=l}^{n} dis(l,i)* (n-i+1),交换i和l的求和顺序,可以得到

ans=Σ_{i=1}^{n}[(n-i+1)Σ_{l=1}^{i} dis(l,i)] 证明如下

打开表达式

n dis(1,1) + (n-1) dis(1,2) + (n-2) dis(1,3) + ... + dis(1,n)
           + (n-2) dis(2,2) + (n-2) dis(2,3) + ... + dis(2,n)
                            + (n-3) dis(3,3) + ... + dis(3,n)
                                               ...
                                                   + dis(n,n)

通过观察发现,原本的式子是横着相加的,由于这个表达式非常对称,因此我们可以竖着相加 就得到了ans=Σ_{i=1}^{n}[ (n-i+1)Σ_{l=1}^{i} dis(l,i) ]

由数学性质,我们只能优化到这一步了,接下来得靠dis的性质

dis代表着l,r有多少个不同的元素

我们观察一个数组

1 2 3 1 2 4 5

显然,这里的i=7,令si=Σ_{l=1}^{i} dis(l,i)

对于nums[1]来说,只有一个数组{1,2,3,1,2,4,5}用到了它,它的贡献为1

对于nums[2]来说,除了上面的以外,还有{2,3,1,2,4,5}用到了它,它的贡献值为2,出现了两次

对于nums[4]来说,显然{1,2,3,1,2,4,5}是没有用到它的贡献的,因为数组重复了,它的贡献需要往后算,也就是3

规律出现了,对于某个数nums[i],它的贡献是i-pre[i],pre[i]表示上一次nums[i]出现的位置,没有出现过则算作0

也就是说si=Σ_{l=1}^{i} (l-pre[l])

再找到si-1和si的关系,显然si-si-1=i-pre[i],也就是si=s(i-1)+i-pre[i]

即ans=Σ_{i=1}^{n}[ (n-i+1) si],且si的平均复杂度是O(1),只需通过预处理,提前算出s[i],可以知道最终复杂度为O(n)

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int>nums(n+1,0);
        unordered_map<int,int>mp;
        vector<int>pre(n+1,0);
        vector<int>sum(n+1,0);
        for(int i=1;i<=n;i++){
            cin>>nums[i];
            if(mp[nums[i]]){
                pre[i]=mp[nums[i]];
            }
            mp[nums[i]]=i;
        }
        sum[1]=1-pre[1];
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1]+i-pre[i];
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            ans+=(n-i+1)*sum[i];
        }
        cout<<ans<<'\n';
    }
}