abc371E I Hate Sigma Problems
给定长度为N的数组A[i]，记f(l,r)表示区间[l,r]内不同A[i]的个数，求所有子区间f(i,j)之和。
1<=N<=2E5, 1<=A[i]<=N
分析：贡献法，为了方便统计，区间中重复的数字以最左边出现的数为准，保证不重不漏。对于A[i]，假设其上一次出现的位置为p，那么包含该数字的左端点可以是p+1,p+2,...,i，右端点可以是i+1,i+2,...,N。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int N;
std::cin >> N;
std::vector<int> A(N + 1);
for (int i = 1; i <= N; i++) {
std::cin >> A[i];
}
std::map<int,int> lst;
i64 ans = 0;
for (int i = 1; i <= N; i++) {
ans += 1LL * (i - lst[A[i]]) * (N - i + 1);
lst[A[i]] = i;
}
std::cout << ans << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}