题面传送门 启发式合并大法好! 你会发现这道题可以暴力合并。 然而数据稍微用心一点就卡掉了。 然后你可以试图优化一下，比如合并时把小的合并到大的上面去。 结果就过了。 这样复杂度上界是 O ( n l o g n ) O(nlogn) O(nlogn)，具体证明在这篇题解里有。 代码实现:
#include<cstdio> #include<cstring> int n,m,k,x,y,z,a[100039],siz[1000039],ans,cur,fa[1000039]; struct yyy{int to,z;}tmp; struct ljb{ int head,h[1000039]; yyy f[2000039]; inline void add(int x,int y){ f[++head]=(yyy){y,h[x]}; h[x]=head; } }s; inline void swap(int &x,int &y){x^=y,y^=x,x^=y;} inline void hebing(int x,int y){ cur=s.h[x]; while(cur!=-1){ tmp=s.f[cur]; ans-=(a[tmp.to-1]==y)+(a[tmp.to+1]==y); cur=tmp.z; } cur=s.h[x]; while(cur!=-1){ tmp=s.f[cur]; a[tmp.to]=y; s.add(y,tmp.to); cur=tmp.z; } siz[y]+=siz[x]; siz[x]=0; s.h[x]=-1; } int main(){ memset(s.h,-1,sizeof(s.h)); register int i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]),s.add(a[i],i),siz[a[i]]++,fa[a[i]]=a[i]; for(i=1;i<=n;i++) if(a[i]!=a[i-1]) ans++; for(i=1;i<=m;i++){ scanf("%d",&x); if(x==1){ scanf("%d%d",&x,&y); if(x==y) continue; if(siz[fa[x]]>siz[fa[y]])swap(fa[x],fa[y]); if(!siz[fa[x]])continue; hebing(fa[x],fa[y]); } else printf("%d\n",ans); } }