P3201梦幻布丁【启发式合并链表】

题意:

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

操作1
表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.
操作2
表示要进行询问当前有多少段颜色

$1 \leq N \leq 1 e 5, 1 \leq X, Y \leq 1 e 6$

思路:

我们可以把每一种颜色的位置用链表存起来，然后每一次改变一种颜色的时候我们就把相应的两种相同的颜色的链表合并成一条，普通的合并链表最差的情况就是 $O (n)$ 的时间复杂度，而采用启发式合并的思想，我们是把小的链表合并到大的链表里面，这样会节省时间复杂度，据说均摊下来每一次合并时间复杂度为 $O (l o g n)$
小技巧：
本次修改后这个链的颜色是1（颜色为2的链被删除了），如果接下来修改颜色 2（显然这是合法的），会使得找不到颜色2而只能找到颜色1了。所以我们需要使用一个f数组，表示当我们要寻找颜色x时，实际上需要寻找颜色为f[x]的链。如果遇到上面这种情况就要交换交换 f[x]和 f[y]。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;//布丁的最大个数
const int maxm = 1e6+5;//颜色的最多数量
int c[maxn], nxt[maxn];//每个布丁的颜色 第i个节点的next点
int st[maxm], hd[maxm], sz[maxm], f[maxm];//初始头节点 尾节点 每种颜色的数量 每个颜色实际代表的颜色
int ans, n, m, op;
void merge(int x, int y) {
	for(int i = hd[x]; i; i = nxt[i]) {//更新答案
		ans -= (c[i-1] == y) + (c[i+1] == y);
	}
	for(int i = hd[x]; i; i = nxt[i]) {
		c[i] = y;
	}
// nxt[st[x]] = hd[y];
// hd[y] = hd[x];
	nxt[st[y]] = hd[x];
	st[y] = st[x];
	sz[y] += sz[x];
	sz[x] = 0;
	hd[x] = 0;
	st[x] = 0;
}
int main() {
	scanf("%d %d", &n, &m);
	ans = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
		ans += (c[i] != c[i-1]);
		f[c[i]] = c[i];//初始化
		if(!hd[c[i]]) {
			st[c[i]] = i;
		}
		nxt[i] = hd[c[i]];//链表插入
		hd[c[i]] = i;
		sz[c[i]]++;
	}
	while(m--) {
		scanf("%d", &op);
		if(op == 2) {
			printf("%d\n", ans);
		} else {
			int x, y;
			scanf("%d %d", &x, &y);
			if(x == y) continue;
			if(sz[f[x]] > sz[f[y]]) {
				swap(f[x], f[y]);
			}
			//x小 插入y大
			if(sz[f[x]] == 0)continue;
			merge(f[x],f[y]);
		}
	}

}