#853 C. Serval and Toxel‘s Arrays

题意：

$n$ 个数（下标从1开始），$m$ 次操作，每一次操作有两个数$p$, $v$，把下标为 $p$ 的数改成 $v$，经过 $m$ 次操作可以得到 $m+1$ 个数组，两两组合，将这些组合里面有多少个不同的元素加起来，输出。

解题：

考虑贡献，一个数 $p$ 在 $x$ 个数组里面出现，那他的贡献就是 $x\ast m-x\ast (x-1)/2$，这个很好想，画图模拟一下就可以了。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

int a[N];
map<LL, LL> lst, mp;

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        lst[a[i]] = 0;
    }
    
    for (int i = 1; i <= m; i ++ )
    {
        int v, p;
        cin >> p >> v;
        mp[a[p]] += i - lst[a[p]];
        lst.erase(a[p]);
        a[p] = v, lst[a[p]] = i;
    }
    
    for (auto [a, b] : lst) mp[a] += m + 1 - b;
    
    LL ans = 0;
    for (auto [_, k] : mp) ans += k * m - k * (k - 1) / 2;
    
    cout << ans << '\n';
    
    mp.clear(), lst.clear();
}

int main()
{
    int T = 1;
    cin >> T;
    while (T -- )
    {
        solve();
    }
    return 0;
}

反思：

与其说是反思倒不如说是提醒，我在做这道题的时候压根就没有去想这道题怎么做，我一直在琢磨我写的暴力输出的结果为什么和样例不一样了，所以之后做题不要把时间浪费在没有必要的地方。