题解：AT_abc371_e [ABC371E] I Hate Sigma Problems
_Leehom_
·
·
题解
题意
$f(l, r)$ 表示 $a_l \dots a_r$ 中有多少个不同的数。
## 解法
看到求和计数题，直接有脑容斥：
显然，总共的情况是 $\sum_{i = 1}^{i \leq n} \sum_{i = 1}^{i \leq n - i + 1} i$。
对每个数值讨论：
如果有两个数值重复出现，那么设两个数值出现的位置为 $i, j$，答案会少 $i \times (n - j + 1)$。如果该数值有多个，那么暴力的去想，枚举 $i, j$，是一个 $O(n^2)$ 的。优化的话就是：枚举 $i$，遍历一遍整个数值 `vector` 做个后缀和，统计位置在 $i$ 之后的数 $j$ 的 $\sum n - j + 1$。然后计算就行了，注意可能会重复减掉一个方案，要注意去重。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, a[N], ans, dfix[N];
vector<int>cnt[N];
int function1(int x){ // 1 + 2 + ... + x = function1(x)
return x + x * x >> 1;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; cin >> a[i++]);
for(int i = 1; i <= n; ++i) cnt[a[i]].push_back(i); // 存进 vector
for(int i = 1; i <= n; ++i) ans += function1(n - i + 1); // 初始时的答案
for(int i = 1; i <= n; ++i){
dfix[cnt[i].size()] = 0;
for(int j = cnt[i].size() - 1; j > -1; --j) dfix[j] = dfix[j + 1] + n - cnt[i][j] + 1; // 处理后缀和
for(int j = 0; j < cnt[i].size(); ++j) ans -= (cnt[i][j] - (j > 0 ? cnt[i][j - 1] : 0)) * dfix[j + 1]; // 减去不合法答案
}
cout << ans;
return 0;
}
```