C++ 解法, 执行用时: 46ms, 内存消耗: 6008K, 提交时间: 2022-04-30 21:07:47

#include<bits/stdc++.h>
using namespace std;
int a[300005],b[1000005];
int main(){
	int t,n,m,i,x,y;
	long long s=0,p;
	memset(b,0,sizeof b);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[a[i]]++;
	}
	for(i=1;i<=1000000;i++){
		p=b[i];
		s+=p*(p-1)*(p-2)/2/3;
	}
	while(m--){
		scanf("%d%d",&x,&y);
		p=b[a[x]];
		s-=3*(p-1)*(p-2)/2/3;
		b[a[x]]--;
		a[x]=y;
		b[a[x]]++;
		p=b[a[x]];
		s+=3*(p-1)*(p-2)/2/3;
		printf("%lld\n",s);
	}
}

Python3 解法, 执行用时: 778ms, 内存消耗: 17728K, 提交时间: 2022-05-28 13:47:16

n,m=map(int,input().split(' '))
a=[0]+list(map(int,input().split(' ')))
arr=[0]*(10**6+1)
ans=0
for i in range(1,n+1):
    arr[a[i]]+=1
for item in arr:
    if item>=3:
        ans+=item*(item-1)*(item-2)//6
for i in range(m):
    x,y=map(int,input().split(' '))
    arr[y]+=1
    arr[a[x]]-=1
    if a[x]!=y:
        ans += (arr[y] - 1) * (arr[y] - 2) // 2
        ans -= (arr[a[x]]) * (arr[a[x]] - 1) // 2
    a[x] = y
    print(ans)