「bzoj4298」「ONTAK2015」Bajtocja - Hash+启发式合并+链表

题目大意

    给定$d$张无向图，每张图都有$n$个点。一开始，在任何一张图中都没有任何边。接下来有$m$次操作，每次操作会给出$a,b,k$，意为在第$k$张图中的点$a$和点$b$之间添加一条无向边。你需要在每次操作之后输出有序数对$(a,b)$的个数，使得$1\le a,b\le n$，且$a$点和$b$点在$d$张图中都连通。

---

题目分析

神奇的Hash降维技巧。
在每张图中，我们给每个点一个连通块标号，属于同一个连通块的点标号相同。第$i$张图第$j$个点标号为$f[i,j]$。
现在我们将不同图的相同点的标号$f[j,i]$串起来，Hash一下得到$Hash[i]$。
若两个点Hash相同，说明它们在$d$张图中均连通。

添加新的边时需要将两个连通块合并，利用启发式合并的技巧，将小连通块合并到大连通块，修改所有小连通块的标号以及Hash值。

现在考虑统计答案。
设某个连通块大小为$s$，每次给连通块增加一个点时需要$+2s+1$，每次给连通块删一个点时需要$-2(s-1)-1$。
那么问题来了，我怎么知道相同连通块的信息呢？
问得好，再Hash一遍，每个相同的Hash值统计大小即可。

据说map<>很慢，那我们用list<>吧。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxd=205,maxn=5005,maxs=262143,Base=10007;

struct node {
	LL v;
	int num;
	node(LL v=0,int num=0):v(v),num(num) {}
};

list<node> L[maxs+1];
vector<int> edges[maxd][maxn];
LL Hash[maxn],Pow[maxd],f[maxd][maxn],size[maxd][maxn];
int ans=0;

void ins(LL v) {
	int pos=v&maxs;
	for(auto &x:L[pos])if(x.v==v) {ans+=x.num*2+1;x.num++;return;}
	ans++,L[pos].push_back(node(v,1));
}

void del(LL v) {
	int pos=v&maxs;
	for(auto it=L[pos].begin(); it!=L[pos].end(); it++) {
		auto &x=*it;
		if(x.v!=v)continue;
		ans-=(x.num-1)*2+1;
		if(--x.num==0)L[pos].erase(it);
		return;
	}
}

void Dfs(int z,int x,int fa,int id) {
	del(Hash[x]),Hash[x]-=Pow[z]*f[z][x];
	f[z][x]=id;
	Hash[x]+=Pow[z]*id,ins(Hash[x]);
	for(int y:edges[z][x])if(y!=fa)Dfs(z,y,x,id);
}

void merge(int z,int x,int y) {
	if(f[z][x]==f[z][y])return;
	if(size[z][f[z][x]]>size[z][f[z][y]])swap(x,y);
	size[z][f[z][y]]+=size[z][f[z][x]];
	edges[z][x].push_back(y),edges[z][y].push_back(x);
	Dfs(z,x,y,f[z][y]);
}

int d,n,m;

int main() {
	d=Get_Int();
	n=Get_Int();
	m=Get_Int();
	Pow[0]=1;
	for(int i=1; i<d; i++)Pow[i]=Pow[i-1]*Base;
	for(int i=1; i<=n; ins(Hash[i++]))
		for(int j=0; j<d; j++)f[j][i]=i,size[j][i]=1,Hash[i]+=Pow[j]*i;
	while(m--) {
		int x=Get_Int(),y=Get_Int(),z=Get_Int();
		merge(--z,x,y);
		printf("%d\n",ans);
	}
	return 0;
}