题目链接?
分析一下题意:给定一个初始数组A,以及m次操作,每一次操作会改变一个A中的数字,一共得到m+1个数组。
现在,要求出任意两个数组两两组合的情况中:所有的不重复数字出现次数的总和。
这道题想了很久,乍一看以为是模拟,手画递归找规律一直没想出来。看了题解思路,发现出发点就错了:因为每个数组中的任意数字不用考虑重复的情况,所以可以化整为零的单独考虑每一个数字对于结果的贡献。
因此,我们需要先统计出每个数字出现的次数,然后统计每个数字的贡献。具体参见代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int &p : a) {
cin >> p;
}
map<int, int> appear;
// preTime用来记录每一个位置上一次出现的时间,默认是0
vector<int> preTime(n);
for (int i = 1; i <= m; i++) {
int op, v;
cin >> op >> v;
--op;
if (a[op] != v) {
appear[a[op]] += i - preTime[op];
preTime[op] = i;
a[op] = v;
}
}
// 跑完操作以后,我们还要把最后一轮的结果加进去
for (int i = 0; i < n; i++) {
appear[a[i]] += m + 1 - preTime[i];
}
int sum = 0;
// 一共m + 1个数组,对于数字num,假设出现cnt次,一共就两种情况:
// 1. 和同样出现过数字num的其他数组组合,可以提供C(cnt, 2)点贡献
// 2. 和没出现过数字num的其他数组组合,可以提供cnt * (m + 1 - cnt)点贡献
for (auto &[num, cnt] : appear) {
sum += (cnt - 1) * cnt / 2;
sum += (m + 1 - cnt) * cnt;
}
cout << sum << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}