单独算贡献-526互联

思路：

　　计算每个数字出现次数，单独求每个数字的贡献,一共有m+1个数组

　　假如出现了5次那就是 (m)+(m-1)+(m-2)+.....+(m-4),用首项加末项乘项数除以二计算,m代表多少个数组，i.second代表每个数字出现次数

　　ans+=(m + m + 1 - i.second) * (i.second) / 2;

　　计算每个数字出现次数需要优化，不然会超时

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

    while (T--)
    {
        int n, m;
        cin >> n >> m;
        map<ll, ll>mp;
        vector<int>a(n + 1);
        for (int i = 1; i <= n; i++)cin >> a[i], mp[a[i]] = m + 1;
        ll ans = 0;
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            cin >> x >> y;
            mp[a[x]] -= m - i + 1;
            a[x] = y;
            mp[a[x]] += m - i + 1;
        }
        for (auto i : mp) {
            ans += (m - 1 + m - i.second + 2) * (i.second) / 2;
        }
        cout << ans << endl;
    }
    return 0;
}