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;
}