CF1789C Serval and Toxel's Arrays
学弟的思路。思路清晰,代码简洁明了,吊打目前80%以上题解。
分析
记录每个数字在多少个数组中出现过,即记录每个数字出现的次数。然后挨个数字计算贡献。对于数字k,当 一个存在数字k的数组 与 另一个存在数字k的数组配对 时,数字k所产生的贡献为1(存在两个k,但根据题意砍掉一个,所以贡献为1);而当 一个存在数字k的数组 与 一个不存在数字k的数组配对 时,数字k产生的贡献也为1(只有一个数字k)。因此,根据所有出现过的数字所出现的次数,就可以算出答案。
代码
//考虑每个数的出现次数
#include<bits/stdc++.h>
#define ll long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define no cout<<"No\n"
#define yes cout<<"Yes\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sol void solve
using namespace std;
ll n,m,a[200005],num[400005];
//num[i]存 一共有几个i
sol(){
memset(num,0,sizeof(num));
cin>>n>>m;
rep(i,1,n){
cin>>a[i];
num[a[i]]=m+1;//假设没有变化操作,初始数组的所有元素都有m+1个
}
int p,v;
//在这个循环中通过每次变化更新出所有元素的出现次数
rep(i,1,m){
cin>>p>>v;
if(a[p]==v) continue;
num[a[p]]-=m-i+1; //此时把a[p]换掉,这个位置以后就不是a[p]了,而是v
a[p]=v;
num[v]+=m-i+1;
}
ll sum=0;
rep(i,1,n+m){
if(num[i]!=0){
//num[i]*(m+1-num[i]):存在数字i的数组与不存在i的数组两两配对,数字i的贡献对于每对数组的贡献为1(一个i与一个其他数,但这个其他数的贡献是在它自己的轮次中计算的,而现在是数字i的轮次,只看i的贡献,是1)
//num[i]*(num[i]-1)/2:存在数字i的数组之间两两配对,数字i对于每对数组的贡献也是1(两个i相同,消掉一个,贡献为1)
sum+=1ll*(num[i]*(m+1-num[i]) + num[i]*(num[i]-1)/2);
}
}
cout<<sum<<"\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)