BZOJ 1483: [HNOI2009]梦幻布丁 [链表启发式合并]

1483: [HNOI2009]梦幻布丁

题意：一个带颜色序列，一种颜色合并到另一种，询问有多少颜色段

---

一种颜色开一个链表，每次遍历小的合并到大的里，顺带维护答案

等等，合并方向有规定？

令col[x]代表给颜色x分配的编号，直接交换编号



WA了三次我还有救吗

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define lc t[x].ch[0]
#define rc t[x].ch[1]
#define pa t[x].fa
const int N=1e5+5, M=1e6+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n, Q, a[N], op, ans, x, y;
struct meow{int v, ne;}e[M];
int cnt, h[M], size[M], col[M];
inline void ins(int u, int v) {
	e[++cnt]=(meow){v, h[u]}; h[u]=cnt; size[u]++;
}
void Merge(int x, int y) { //printf("Merge %d %d\n",x,y);
	if(x==y) return;
	if(size[col[x]]>size[col[y]]) swap(col[x], col[y]);
	x=col[x], y=col[y]; //printf("col %d %d\n",x,y);
	for(int i=h[x];i;i=e[i].ne) {
		int v=e[i].v; //printf("vvv %d\n",v);
		ans-= (a[v-1]==y) + (a[v+1]==y);
		ins(y, v);
	}
	for(int i=h[x];i;i=e[i].ne) a[e[i].v]=y;
	h[x]=size[x]=0;
}
int main() {
	freopen("in","r",stdin);
	n=read(); Q=read();  ans=n;
	for(int i=1; i<=n; i++) a[i]=read(), ins(a[i], i), ans-= a[i]==a[i-1], col[a[i]]=a[i];
	for(int i=1; i<=Q; i++) {
		op=read();
		if(op==1) x=read(), y=read(), Merge(x, y);
		else printf("%d\n",ans);
	}
}