ABC- 371 - E- I Hate Sigma Problems · znzryb
<!-- Notion block type: table_of_contents -->
## AC代码
```cpp
3
1 2 2
```
看我手算样例
主要思路写在注释当中，具体来说就是算贡献度
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,A[N],vis[N],dp[N],ans,fsum,give[N]; // give[i] 表示i位置对个数的贡献到几位置为止
ll valP[N]; // 值对应位置，比如说5这个值上次在4位置出现过，那么就 valP[5]=4，没出现过自然是0；
bool vis2[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>A[i];
}
for(int i=1;i<=n;i++) // give 初始化
give[i]=n+1; // give[i] 表示i位置对个数的贡献到几位置为止
for(int i=1;i<=n;i++) {
ll ai=A[i];
give[valP[ai]]=i;
valP[ai]=i;
if(vis[A[i]]==0)
dp[i]=dp[i-1]+1,fsum+=dp[i],vis[A[i]]+=1;
else
dp[i]=dp[i-1],fsum+=dp[i],vis[A[i]]+=1;
}
ans+=fsum;
// cout<<ans<<endl;
for(int i=2;i<=n;i++) {
fsum=fsum-(1+give[i-1]-i); // 第一个1代表少了一个长度，自然要少一个（那一个即【i-1，i-1】）
// 然后我们关注的是失去的i-1的贡献域
ans+=fsum;
// cout<<i<<":"<<fsum<<endl;
}
cout<<ans<<endl;
// debug();
}
// AC https://atcoder.jp/contests/abc371/submissions/59306953
```
## 心路历程（WA，TLE，MLE……）
### 对拍暴力程序（不用多说，肯定超时）
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,A[N],dp[N],ans,fsum,diff[N],cnt=0;
bitset<N> vis;
void debug() {
for(int i=1;i<=n;i++) {
cout<<dp[i]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>A[i];
}
for(int i=1;i<=n;i++) {
cnt=0;vis.reset();
for(int j=i;j<=n;j++) {
if(!vis[A[j]])
cnt++,ans+=cnt,vis[A[j]]=true;
else
ans+=cnt;
}
}
cout<<ans<<endl;
}
```
### 贪心有偏差做法，偏差在这个部分
其实复杂的样例都通不过
```cpp
}else {
fsum-=1;
ans+=fsum;
cout<<i<<":"<<fsum<<endl;
}
```
虽然从最后一位看上去 i 位置是没有贡献的（在个数上），但前面的某些位其实是有在个数上的贡献的
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,A[N],vis[N],dp[N],ans,fsum,diff[N];
bool vis2[N];
void debug() {
for(int i=1;i<=n;i++) {
cout<<dp[i]<<" ";
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>A[i];
}
for(int i=1;i<=n;i++) {
if(vis[A[i]]==0)
dp[i]=dp[i-1]+1,fsum+=dp[i],vis[A[i]]+=1;
else
dp[i]=dp[i-1],fsum+=dp[i],vis[A[i]]+=1;
}
ans+=fsum;
cout<<ans<<endl;
for(int i=2;i<=n;i++) {
vis[A[i-1]]-=1;
if(vis[A[i-1]]<=0) {
fsum=fsum-1-(n-i+1);
cout<<i<<":"<<fsum<<endl;
ans+=fsum;
}else {
fsum-=1;
ans+=fsum;
cout<<i<<":"<<fsum<<endl;
}
}
cout<<ans<<endl;
debug();
}
```