题解 | #权值计算#

H题题解：

用C++语言还原伪代码：

int function(int l,int r int s[]){
    int total=0;
    set<int>dis;
    int count=0;
    for(int i=l;i<=r;i++){
        if(dis.find(s[i])==dis.end()){
            count++;
        }
        total+=count;
    }
    return total;
}

题目解析：

权值表示的是数组s所有前缀的元素种类之和。通过遍历计算每个元素对每个子数组的贡献值：例如数组 [1 1 4 5 1 4]，对于第一个数s[1]，当计算它对每个子数组的贡献值时，我们首先分析它的L和R的范围，0<L<=1,R>=1;当L=1时，s[1]在子数组[1]权值中的贡献值为1，s[1]在子数组[1 1]权值中的贡献值为1+1=2(我们忽略后面与s[1]相同的元素贡献值，只计算该元素第一次出现的贡献值)，s[1]在子数组[1 1 4]权值中的贡献值为1+1+1=3，s[1]在子数组[1 1 4 5]权值中的贡献值为1+1+1+1=4，s[1]在子数组[1 1 4 5 1]权值中的贡献值为1+1+1+1+1=5，s[1]在子数组[1 1 4 5 1 4]权值中的贡献值为1+1+1+1+1+1=6；由此可见s[1]在所有子数组权值中的贡献值：1，2，3，4，5，6 是一个公差为1的等差数列。接下来再列举第五个数s[5]=1，要想计算他对数组的贡献值，需要让这个值在s[5]位置是第一次出现，所以他的5>=L>=3,R>=5.当L取不同值时，分别得到一串等差数列。 代码演示：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
const int N = 100010;
int a[N];
void solve(){
	int n,sum=0,tmp=0,l1,l2,r1,r2,d;
	cin>>n;
	map<int ,int>mp;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		if(mp.find(a[i])!=mp.end()){//若当前元素之前出现过，则l1=该元素之前最后一次出现的位置+1；
			l1=mp[a[i]]+1;
		}else{
			l1=1;//若之前没有出现过，l1从1开始
		}
		l2=i;
		r1=i;
		r2=n;
		d=r2-r1+1;//等差元素个数
		tmp=d+d*(d-1)/2;//等差数列求和
		sum+=tmp*(l2-l1+1);//l2-l1+1代表有几个这样的等差数列
		mp[a[i]]=i;//记录当前元素出现的最新位置
	}
	cout<<sum<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;cin>>T;
	while(T--){
		solve();
	}
	return 0;
}