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;
}