P8026题解

strlen_s_ · 2023-01-16 23:30:14 · 题解

WC 第二课堂的题目选讲讲了这题，感觉非常妙，特写一篇题解总结。

分析

题目要求每张图都联通，观察 m 发现很大，所以枚举每张图不显示，于是可以参考 CSP-S T3 的思路，给每张图的每个点随机赋一个点权，然后哈希。

现在考虑如何哈希。

我们发现题目要求我们维护一个连边的操作，自然而然想到用并查集维护，那么每个点有一个指向的父亲。对于这种唯一确定的关系，我们就可以在这个方面设计哈希值。

设 sum_i 表示 i 在每张图中父亲的点权之和。倘若 a 与 b 的 sum_i 相同，那么它们大概率在每张图中都有相同的父亲，所以它们在每张图中联通，对答案有贡献。

然后开一个桶用来跟新答案，然后再写一个启发式合拼。

复杂度 O(m \log dn)，但常数巨大，要吸氧。

#include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
using namespace std;
in int read(){
    int x=0,f=1;
    char c;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=5e3+10,D=205,mod=2e9;
int w[D][N];
vector<int>st[D][N];
int f[D][N],sum[N];
int d,n,m;
unordered_map<int,int>mp;
int ans;
int add(int sum,int x,int z){
    sum-=mp[x]*mp[x];
    mp[x]+=z;
    sum+=mp[x]*mp[x];
    return sum;
}
signed main(){
    srand(time(0));
    d=read(),n=read(),m=read();
    for(int i=1;i<=d;i++)for(int j=1;j<=n;j++)w[i][j]=rand()*rand()%mod;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=d;j++)
            st[j][i].push_back(i),f[j][i]=i,sum[i]+=w[j][i];
        ans=add(ans,sum[i],1);
    }
    while(m--){
        int x=read(),y=read(),p=read();
        x=f[p][x],y=f[p][y];
        if(x==y){
            printf("%lld\n",ans);
            continue;
        }
        if(st[p][x].size()<st[p][y].size())swap(x,y);
        for(auto i:st[p][y]){
            st[p][f[p][x]].push_back(i);
            ans=add(ans,sum[i],-1);
            sum[i]=sum[i]-w[p][f[p][i]]+w[p][f[p][x]];
            ans=add(ans,sum[i],1);
            f[p][i]=f[p][x];
        }
        st[p][y].clear();
        printf("%lld\n",ans);
    }
    return 0;
}