题解：CF1527C Sequence Pair Weight
zzmbj
·
·
题解
CF1527C
思路
对于每一对相等的元素 (p, q)，考虑多少个区间会包含这一对。(p, q) 对最终答案的贡献就是包含它的区间个数。
区间 [L, R] 要包含 p, q 必须满足 L\le p, R\ge q。
$R$ 可以选 $q,q+1,\ldots,n$，共 $n-q+1$ 种可能。
包含 $(p, q)$ 的区间个数就是 $p\times (n-q+1)$。
最终答案：
$$
\text{ans} = \sum_{q=1}^n\sum_{\begin{subarray}{c} p<q, a_p=a_q
\end{subarray}} p \times (n-q+1)
$$
考虑枚举右端点 $q$，累加左端点的贡献。
$$
S_q = (n-q+1)\times \sum_{p<q, a_p=a_q} p
$$
### 代码
```cpp lines=12-13
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, ans, a[100005];
signed main()
{
cin >> n;
map<ll, ll> num;
for(int i=1; i<=n; i++)
{
cin >> a[i];
ans += num[a[i]] * (n-i+1); //以P结尾相似对贡献：ans += a[1~n] * (n+1-p)
num[a[i]] += i;
}
cout << ans;
return 0;
}
```
### 彩蛋
[双倍经验](https://www.luogu.com.cn/problem/B4453)。