题目
(n)个布丁摆成一行，进行(m)次操作。
每次将某个颜色的布丁全部变成另一种颜色的，
然后再询问当前一共有多少段颜色。
（(n,mleq 10^5,colleq 10^6)）
分析
考虑用链表存储每一种颜色的位置，由于颜色总数只会减少不会增多，
考虑启发式合并，将个数小的合并到个数大的，并交换实际的颜色表示，
时间复杂度(O(nlog_2n))
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
const int N=1000011;
int ls[N],st[N],cnt[N],col[N/10],f[N],nxt[N/10],n,m,ans;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline void Turn_Into(int x,int y){
for (rr int i=ls[x];i;i=nxt[i]) ans-=(col[i-1]==y)+(col[i+1]==y);//如果相邻块数减小
for (rr int i=ls[x];i;i=nxt[i]) col[i]=y;//更改颜色
nxt[st[x]]=ls[y],ls[y]=ls[x],cnt[y]+=cnt[x],ls[x]=st[x]=cnt[x]=0;//更新链表
}
signed main(){
n=iut(); m=iut();
for (rr int i=1;i<=n;++i){
col[i]=iut(),ans+=col[i]!=col[i-1];
if (!ls[col[i]]) st[col[i]]=i,f[col[i]]=col[i];
++cnt[col[i]],nxt[i]=ls[col[i]],ls[col[i]]=i;
}
while (m--){
rr int opt=iut();
if (opt==2) print(ans),putchar(10);
else{
rr int x=iut(),y=iut();
if (x==y) continue;//颜色相同不需要合并
if (cnt[f[x]]>cnt[f[y]])
f[x]^=f[y],f[y]^=f[x],f[x]^=f[y];//个数小的合并到个数大的
if (!cnt[f[x]]) continue;//不需要合并
Turn_Into(f[x],f[y]);
}
}
return 0;
}