算法
(模拟) $O(n)$
固定 $j$,把 $j - a_j\text{在此之前出现的个数}$ 加入答案。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::map;
using std::vector;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
map<int, int> mp;
ll ans = 0;
rep(j, n) {
ans += j - mp[a[j]];
mp[a[j]]++;
}
cout << ans << '\n';
return 0;
}