因为是把所有颜色x都变成颜色y，所以把颜色y变成颜色x也是可以的
那么每次呢，就是要把两种颜色合并
记录一下每个颜色当前存在哪个链表里，启发式合并链表就好了
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 100010 #define MAXM 1000010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long int n,m; int a[MAXN]; vector<int>ps[MAXM]; int ans; int c[MAXM]; int main(){ int i; int o,x,y; scanf("%d%d",&n,&m); for(i=1;i<MAXM;i++){ c[i]=i; } for(i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]!=a[i-1]){ ans++; } ps[a[i]].push_back(i); } while(m--){ scanf("%d",&o); if(o==1){ scanf("%d%d",&x,&y); if(x==y){ continue ; } if(ps[c[x]].size()>ps[c[y]].size()){ swap(c[x],c[y]); } x=c[x]; y=c[y]; for(i=0;i<ps[x].size();i++){ if(a[ps[x][i]-1]==y){ ans--; } if(a[ps[x][i]+1]==y){ ans--; } } for(i=0;i<ps[x].size();i++){ a[ps[x][i]]=y; ps[y].push_back(ps[x][i]); } ps[x].clear(); } if(o==2){ printf("%d\n",ans); } } return 0; } /* */
