1 #include
     
       2 #include
      
        3 #include
       
         4 #define M 1000008 5 using namespace std; 6 int n,next[M],ft[M],m,sum,head[M],st[M],s[M],c[M]; 7 int main() 8 { 9     scanf("%d%d",&n,&m);10     for(int i=1;i<=n;i++)11       {12         int a1;13         scanf("%d",&c[i]);14         if(c[i]!=c[i-1])15           sum++;16         ft[c[i]]=c[i];17         if(!head[c[i]])18           st[c[i]]=i;19         s[c[i]]++;20         next[i]=head[c[i]];21         head[c[i]]=i;22       }23     for(int i=1;i<=m;i++)24       {25         int a1,a2,a3;26         scanf("%d",&a1);27         if(a1==2)28           printf("%d\n",sum);29         else30           {31             scanf("%d%d",&a2,&a3);32             if(a2==a3)continue;33             if(s[ft[a2]]>s[ft[a3]])34               swap(ft[a2],ft[a3]);35             int a=ft[a2],b=ft[a3];36             if(!s[a])37               continue;38             s[b]+=s[a];39             for(int j=head[a];j;j=next[j])40               {41                 if(c[j+1]==b)42                   sum--;43                 if(c[j-1]==b)44                   sum--;45               }46             for(int j=head[a];j;j=next[j])47               c[j]=b;48             next[st[a]]=head[b];49             head[b]=head[a];50             head[a]=s[a]=st[a]=0;51           }52       }53     return 0;54 }
       
      
     

链表合并，启发式合并，由于是启发式合并，所以还要开一个数组记录实际是哪个颜色。