感觉很早以前就被黈力教导过启发式合并

根本不懂为什么这样就log了呢

其实就是把小的那部分并到大的那部分呢

1483: [HNOI2009]梦幻布丁

唔。。邻接表和启发式合并

然后就没有辣

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;

#define NN 1000005

int read()
{
	char ch; int f=1,xx=0;
	for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
	for (xx=0;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=f;
	return xx;
}

int n,m,fa[NN],c[NN],a[NN],head[NN],ne[NN],now[NN],tmp,x,y,type,ans=0;

int main()
{
	n = read(), m = read();
	for (int i=1;i<=n;++i)
	{
		a[i] = read();
		c[a[i]] ++;
		fa[a[i]] = a[i];
		if (a[i] != a[i-1]) ++ans;
		if (!head[a[i]]) head[a[i]] = i;
		ne[now[a[i]]] = i;
		now[a[i]] = i;
	}
	while (m--)
	{
		type = read();
		if (type == 2) printf("%d\n", ans);
		else
		{
			x = read() , y = read();
			if (x == y) continue;
			if (c[fa[x]] > c[fa[y]]) swap(fa[x], fa[y]);
			x = fa[x], y = fa[y];
			if (c[x] == 0) continue;
			for (int i=head[x]; i ; i=ne[i])
			{
				tmp=i;
				if (y == a[i+1]) ans--;
				if (y == a[i-1]) ans--;
			}
			for (int i=head[x]; i ; i=ne[i]) a[i] = y;
			ne[tmp] = head[y], head[y] = head[x], c[y] += c[x], head[x] = c[x] = 0;
		}
	}
	return 0;
}