对于每一个颜色用一个链表存储，并记录下：1.当前某种颜色的真实颜色；2.这种颜色的数量（用于启发式合并的判断）；3.当前答案（即有几段），然后对于每一个操作简单处理一下就行了。

1 #include
      
        2 using namespace std; 3 #define N 1000005 4 int n,m,ans,p,x,y,head[N],tru[N],sum[N],nex[N],last[N],a[N]; 5 void merge(int x,int y){ 6     for(int i=head[x];i!=-1;i=nex[i])ans-=(a[i-1]==y)+(a[i+1]==y); 7     for(int i=head[x];i!=-1;i=nex[i])a[i]=y; 8     sum[y]+=sum[x]; 9     nex[last[y]]=head[x];10     last[y]=last[x];11     head[x]=-1;12     sum[x]=last[x]=0;13 }14 int main(){15     scanf("%d%d",&n,&m);16     memset(head,-1,sizeof(head));17     for(int i=1;i<=n;i++)scanf("%d",&a[i]);18     for(int i=n;i;i--){19         if (a[i]!=a[i-1])ans++;20         tru[a[i]]=a[i];21         if (head[a[i]]==-1)last[a[i]]=i;22         sum[a[i]]++;23         nex[i]=head[a[i]];24         head[a[i]]=i;25     }26     for(int i=1;i<=m;i++){27         scanf("%d",&p);28         if (p==2)printf("%d\n",ans);29         else{30             scanf("%d%d",&x,&y);31             if (sum[tru[x]]>sum[tru[y]])swap(tru[x],tru[y]);32             if ((x!=y)&&(sum[tru[x]]))merge(tru[x],tru[y]);33         }34     }35 }