CF1527C Sequence Pair Weight(思维)

题目传送门

题意

给你一个序列，请你求出 ∑ 1 < = i < j < = n ∑ i < = x < y < = j [ a x = = a y ] \displaystyle\sum_{1<=i<j<=n}^{}\displaystyle\sum_{i<=x<y<=j}^{}[a_x==a_y] 1<=i<j<=n∑​i<=x<y<=j∑​[ax​==ay​]

思路

这道题实际上就是让计算贡献，两个数，每枚举的数字中，右边给的贡献是 n − i + 1 n-i+1 n−i+1左边给的贡献则是前缀和（因为要求计算的是所有的子区间)

比如

1 0 1 1

那么第三个1可以选择和第二个1组合（可选i=3个位置），也可以和第一个1组合（可以选i=1个位置），因此1+3就是前缀和

AC代码

#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
		ll ans=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			ll u;
			cin>>u;
			ans+=(n-i+1)*mp[u];
			mp[u]+=i;
		}
		cout<<ans<<endl;
	}
}