启发式合并

暴力的优化？

简介：

• 类似于并查集的按积合并。
• 思想：观察每个元素，计算最终计算量的贡献
• 时间复杂度：对于每个元素所在集合进行合并，最终进行 $n >> i$ 的合并，可见最多只会合并 $\log n$次，最坏情况下会合并 $n$ 个数， 故时间复杂度为 $O(n \log n)$ 。

操作方法：

• 将两个数据结构合并时，应将小的数据结构中的元素一个一个分别插入大的数据结构（真的好像就这个）。

例题P3201 [HNOI2009] 梦幻布丁：

solution：

• 不难看出这道题就只需要瞎暴力就可以（被毒瘤hack了，为什么线段树合并没有被hack？）
• 虽然暴力被干点掉了，但这道题我们好像也想不到什么奇奇怪怪的算法，那么正解只有一个——优化暴力。
• 怎么优化呢，我们考虑将每一种颜色拉成链，每次只将小的链接到大的链上，这样貌似巨快雾，但是我们的正确性呢？如图：

• 如果我们考虑讲1接到2上，2接到3上的话，无疑会发现，当我们将1接到2上的时候，实际上是将2接到1上，而我们要将2接到3上时，2已经空了。所以单是这样的做法的话，正确性是有误的，我们不得不考虑如何修正。
• 事实上，2接到1上是可取的，我们只需要离散化出一个数组，用它来存储元素的实际颜色，再用另一个数组指向它所对应的颜色即可，我们按照如图所示的方式将2接到1上：

• 不难发现，此时2的实质颜色是1，再将3接到2所对的1下方就完全没有问题了。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m;
int idx;
int h[M], e[M], ne[M];
int color[M], sz[M], p[M];
int ans;
template <class T>
inline void read(T &res)
{
	res = 0; bool flag = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-') flag = 1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + c - '0', c = getchar();
	if(flag) res = -res;
} 
void add(int x, int y)
{
	idx ++;
	e[idx] = y, ne[idx] = h[x], h[x] = idx;
	sz[x] ++;
}
void merge(int &x, int &y)
{
	if(x == y) return ;
	if(sz[x] > sz[y]) swap(x, y);
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i];
		ans -= (color[j - 1] == y) + (color[j + 1] == y);
	}
	for(int i = h[x]; ~i;i = ne[i])
	{
		int j = e[i];
		color[j] = y;
		if(ne[i] == -1)
		{
			ne[i] = h[y], h[y] = h[x];
			break;
		}
	}
	h[x] = -1;
	sz[y] += sz[x], sz[x] = 0;
}
int main()
{
	read(n), read(m);
	memset(h, -1, sizeof(h));
	for(int i = 1;i <= n;i ++)
	{
		read(color[i]);
		if(color[i] != color[i - 1]) ans ++;
		add(color[i], i);
	}
	for(int i = 0;i < M;i ++) p[i] = i;//离散化，必须初始化到M
	while(m --)
	{
		int op;
		read(op);
		if(op == 2) printf("%d\n", ans);
		else
		{
			int x, y;
			read(x), read(y);
			merge(p[x], p[y]);
		}
	}
	return 0;
}