数据网站建设成本,校园网站建设情况通报,查企业免费查询,厦门 外贸公司做网站传送门: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比赛的时候感觉已经想到了正解,但是没有想的很清楚,所以赛时没有打出来.
我认为这道题的突破口其…传送门: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比赛的时候感觉已经想到了正解,但是没有想的很清楚,所以赛时没有打出来.
我认为这道题的突破口其实是在ainma_inmainm这里的.有了这个,所以我们最终的算法能够不是n2n^2n2,但是赛时我甚至没有注意到这一点(笑
对于每一个数组中的一个数字来说,我们考虑计算这个数字在其他所有数组中的贡献.我们会发现当这个数字不在其他数组中的时候,显然我们可以得到一个贡献,但是当我们的这个数字在其他数组中的时候,我们此时的这个数字在这个数组中是没有贡献的.我们可以先假装这个数字在其他数组中是没有的,那么此时我们的总贡献就是m∗(1m)/2m*(1m)/2m∗(1m)/2(一共有m1个数组).但是我们此时可能有一种情况就是有重复数字的贡献,所以我们考虑将这个重复数字的贡献减掉.我们可以计算出在所有m1m1m1个数组中这个数字的个数cntcntcnt,那么对于所有的数组来说,我们之前所重复计算的就是cnt∗(cnt−1)cnt*(cnt-1)cnt∗(cnt−1)[也就是这cnt个数组两两配对的个数],那么此时我们的这个数字的总贡献就是m∗(m1)/2−cnt∗(cnt−1)m*(m1)/2-cnt*(cnt-1)m∗(m1)/2−cnt∗(cnt−1)
所以我们此时的问题就变成了如何计算出这么多的数组里面每一个数字的个数.每一次更改时,我们可以使用lastlastlast数组来记录上一次该数字出现的位置,然后计算一下这个数字知道消失所存在的数组此处即可.并且需要注意的我们还需要累计每一个数字一直到最后的存在的次数
下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000000
const double eps1e-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 i1;inm;i) {last[i]-1;cnt[i]0;}
}
signed main() {Tread();while(T--) {nread();mread();init();for(int i1;in;i){a[i]read();last[a[i]]0;} for(int i1;im;i) {int posread(),valread();cnt[a[pos]]i-last[a[pos]];last[a[pos]]-1;last[val]i;a[pos]val;}for(int i1;inm;i) {if(last[i]!-1) {cnt[i](m1-last[i]);}}ll ans2*n*(m1)*(m)/2;for(int i1;inm;i) {ans-cnt[i]*(cnt[i]-1)/2;}printf(%lld\n,ans);}return 0;
}
