Codeforces Round #853 (Div. 2) C. Serval and Toxel‘s Arrays【统计次数，算贡献】

链接
传送门
分析
这道题想法其实很简单，样例的计算方法一定要看懂。以样例1为例，根据他的操作方法可以得到两个新的数组，和一个原来的数组，总共三个数组。
1 2 3
4 2 3
4 5 3
他们两两配对去重，求出总的value。由于每个数组内的各个数各不相同，也就是对于某个数字在一个数组内最多出现一次，只需要统计一下这个数出现的次数就可以知道这个数在多少个数组内，假设我们已经统计到了这个数的出现次数记作m，数组总数记作n，那么在所有的配对中，这个数字的贡献是多少？
包含这个数字的配对有两种，一种是两个都是这个数，一种是只有一个这个数，例如4的贡献，一种是4-4, 另一种是4-1,4-1。其他的配对不含4没有4的贡献。
$取一个数的贡献是这个数个数乘以其他数的个数，即m(n-m)$
$取两个相同的个数的数是C_m^2$
$故总贡献是C_m^2+m(n-m)$
如何着手统计。
我们发现，每次更新都会另起一段，这些出现的次数都是一段一段的，所以我们开一个数组记录上一次更新的位置，每次另一起一段的时候更新位置，并把旧的一段统计如数组即可。注意，最后残余的要清理干净。
实现

#include <bits/stdc++.h>
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 4e5 + 5;
int cnt[N], st[N], a[N];
void solve() {int n, m;cin >> n >> m;for (int i = 1; i <= n + m; i++) cnt[i] = 0, st[i] = 0;for (int i = 1; i <= n; i++) {int c;cin >> c;a[i] = c;}for (int i = 1; i <= m; i++) {int p, v;cin >> p >> v;if (v != a[p]) cnt[a[p]] += i - st[p], st[p] = i;//一定要不等于a[p] = v;}for (int i = 1; i <= n; i++) {//残余部分cnt[a[i]] += m - st[i] + 1;//坐标相减要加1}ll ans = 0;for (int i = 1; i <= n + m; i++) {ans += 1ll * cnt[i] * (m + 1 - cnt[i]);ans += 1ll * cnt[i] * (cnt[i] - 1) / 2;}cout << ans << '\n';
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}