数学

考虑对于每个值 $x$ 求贡献：

• 拿出一个包含 $x$ 的序列和一个不包含 $x$ 的序列，贡献为 $1$。
• 拿出两个包含 $x$ 的序列，贡献为 $1$。

共有 $m+1$ 个序列，如果有 $s_x$ 个序列中包含 $x$，那么对答案的贡献为

$$s_x \times (m-s_x+1) + \dfrac{s_x \times (s_x-1)}{2}$$

而 $s_x$ 是容易统计的，由于 $n,m$ 同阶且使用了 map，总体时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[200'005];
void solution(){
    map<int,int> s,w,ex;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],++w[a[i]],ex[a[i]]=0;
    for(int i=1;i<=m;i++){
        static int x,y;
        cin>>x>>y;
        if(--w[a[x]]==0) s[a[x]]+=i-ex[a[x]];
        a[x]=y;
        if(++w[a[x]]==1) ex[a[x]]=i;
    }
    for(auto i:w) if(i.second) s[i.first]+=m-ex[i.first]+1;
    long long ans=0ll;
    for(auto i:s) ans+=i.second*(i.second-1ll)/2+i.second*(m-i.second+1ll);
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}