【bzoj1483】 HNOI2009—梦幻布丁

http://www.lydsy.com/JudgeOnline/problem.php?id=1483 (题目链接)

题意

　　$n$个布丁摆成一行,进行$m$次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.

Solution

　　链表启发式合并。由于size大小而要交换两个链表的时候有点蛋疼，需要开一个数组来存当前颜色的实际颜色是什么。

细节

　　数据范围$10^6$

代码

// bzoj1483

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)

using namespace std;

const int maxn=1000010;

int size[maxn],head[maxn],next[maxn],c[maxn],fa[maxn];

int n,m,ans;

void merge(int x,int y) {

	for (int i=head[x];i;i=next[i]) {

		if (c[i-1]==y) ans--;

		if (c[i+1]==y) ans--;

	}

	for (int i=head[x];i;i=next[i]) {

		c[i]=y;

		if (!next[i]) {next[i]=head[y],head[y]=head[x];break;}

	}

	size[y]+=size[x];head[x]=size[x]=0;

}

int main() {

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++) {

		scanf("%d",&c[i]);

		if (c[i]!=c[i-1]) ans++;

		fa[c[i]]=c[i];

		next[i]=head[c[i]],head[c[i]]=i;

		size[c[i]]++;

	}

	for (int op,x,y,i=1;i<=m;i++) {

		scanf("%d",&op);

		if (op==2) printf("%d\n",ans);

		if (op==1) {

			scanf("%d%d",&x,&y);

			if (size[fa[x]]>size[fa[y]]) swap(fa[x],fa[y]);

			x=fa[x],y=fa[y];

			if (x==y || size[x]==0) continue;

			merge(x,y);

		}

	}

	return 0;

}