因为是启发式合并所以小的接到大的上。比如把1染成2但是s[1]s[2]s[1]s[2]s[1]s[2]这时我们应该将2合并到1的链后面但是会遇到一个麻烦的问题就是这个链头是接1下的也就是说以后找颜色2发现没有颜色2只有颜色1于是我们应该开一个数组f表示我们寻找一种颜色时实际应该找哪个颜色下的链遇到上面那种情况要交换f[1]f[1]f[1]和f[2]f[2]f[2]。实际操作过程中操作把逻辑颜色 1 染成逻辑颜色 2。但物理上颜色 1 的集合更大所以实际做的是把物理颜色 2 合并到物理颜色 1。合并后物理颜色 1 的链拥有全部布丁。物理颜色 2 的链为空。同时交换了f[1]f[1]f[1]和f[2]f[2]f[2]于是f[1]2f[1] 2f[1]2f[2]1f[2] 1f[2]1所以以后要找逻辑颜色 2 → 查f[2]1f[2] 1f[2]1→ 去物理颜色 1 的链找。✅要找逻辑颜色 1 → 查f[1]2f[1] 2f[1]2→ 去物理颜色 2 的链找此时为空。✅为什么此时2链为空呢因为传入merge的是交换后的值在merge函数中清空了链x的东西。#includebits/stdc.husingnamespacestd;#definelllonglongconstll N1e65;ll n,m,a[N],ans;ll nxt[N],head[N],to[N],siz[N],col[N],en[N],f[N];voidmerge(ll x,ll y){// colx - colyfor(ll ihead[x];i;inxt[i]){ans-(a[i-1]y)(a[i1]y);}for(ll ihead[x];i;inxt[i]){a[i]y;}nxt[en[x]]head[y];head[y]head[x];siz[y]siz[x],siz[x]0,en[x]0,head[x]0;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(ll i0;iN;i)nxt[i]0,head[i]0,f[i]i;ans0;for(ll i1;in;i){cina[i];if(!head[a[i]])en[a[i]]i;if(a[i]!a[i-1])ans;nxt[i]head[a[i]];head[a[i]]i;siz[a[i]];}for(ll i1;im;i){ll op,x,y;cinop;if(op1){cinxy;if(xy)continue;if(siz[f[x]]siz[f[y]])swap(f[x],f[y]);if(!siz[f[x]])continue;merge(f[x],f[y]);}else{coutans\n;}}return0;}