有关并查集

查询了 OI-wiki 后，我们知道只写路径压缩而不写启发式合并时，最坏情况下，复杂度是单次log级别的。于是我快乐的以为可以减少一些码量双log通过此题，但是却不幸92分，下载数据后，我发现

CPP

inline int find(int t,int x) {
	cnt++;
	int temp=query(rt[t],1,n,x);
	if(temp==x) return x;
	int res=find(t,temp);
	rt[t]=update(rt[t],1,n,x,res);
	return res;
}

在进行最多24000次find后，cnt已经来到了4977463了，这显然不符合log级别的数据量，这是怎么一回事呢。有没有大佬能解决我的问题

讨论操作

回复

相关推荐

有关并查集