赛后补题:CF1789C Serval and Toxel‘s Arrays

传送门:CF

题目描述:

题目较长,此处省略
输入:
3
3 2
1 2 3
1 4
2 5
1 1
1
1 1
10 10
4 6 9 12 16 20 2 10 19 7
1 3
5 4
2 17
2 18
6 11
7 1
8 17
5 5
5 5
2 2
输出:
13
1
705

比赛的时候感觉已经想到了正解,但是没有想的很清楚,所以赛时没有打出来.

我认为这道题的突破口其实是在$a_i<=n+m$这里的.有了这个,所以我们最终的算法能够不是$n^2$,但是赛时我甚至没有注意到这一点(笑

对于每一个数组中的一个数字来说,我们考虑计算这个数字在其他所有数组中的贡献.我们会发现当这个数字不在其他数组中的时候,显然我们可以得到一个贡献,但是当我们的这个数字在其他数组中的时候,我们此时的这个数字在这个数组中是没有贡献的.我们可以先假装这个数字在其他数组中是没有的,那么此时我们的总贡献就是$m\ast (1+m)/2$(一共有m+1个数组).但是我们此时可能有一种情况就是有重复数字的贡献,所以我们考虑将这个重复数字的贡献减掉.我们可以计算出在所有$m+1$个数组中这个数字的个数$cnt$,那么对于所有的数组来说,我们之前所重复计算的就是$cnt\ast (cnt-1)$[也就是这cnt个数组两两配对的个数],那么此时我们的这个数字的总贡献就是$m\ast (m+1)/2-cnt\ast (cnt-1)$

所以我们此时的问题就变成了如何计算出这么多的数组里面每一个数字的个数.每一次更改时,我们可以使用$last$数组来记录上一次该数字出现的位置,然后计算一下这个数字知道消失所存在的数组此处即可.并且需要注意的我们还需要累计每一个数字一直到最后的存在的次数

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int T;int n;int m;int last[maxn];
int a[maxn];int cnt[maxn];
void init() {for(int i=1;i<=n+m;i++) {last[i]=-1;cnt[i]=0;}
}
signed main() {T=read();while(T--) {n=read();m=read();init();for(int i=1;i<=n;i++){a[i]=read();last[a[i]]=0;} for(int i=1;i<=m;i++) {int pos=read(),val=read();cnt[a[pos]]+=i-last[a[pos]];last[a[pos]]=-1;last[val]=i;a[pos]=val;}for(int i=1;i<=n+m;i++) {if(last[i]!=-1) {cnt[i]+=(m+1-last[i]);}}ll ans=2*n*(m+1)*(m)/2;for(int i=1;i<=n+m;i++) {ans-=cnt[i]*(cnt[i]-1)/2;}printf("%lld\n",ans);}return 0;
}