1 条题解
-
1
#include <iostream> #include <cstdio> const int N=1e5+5,M=1e6+5; int n,m,c[N],sz[M],st[M],f[M],hd[M],nxt[N],ans; void merge(int x,int y) { for(int i=hd[x];i;i=nxt[i]) ans-=(c[i-1]==y)+(c[i+1]==y); for(int i=hd[x];i;i=nxt[i]) c[i]=y; nxt[st[x]]=hd[y],hd[y]=hd[x],sz[y]+=sz[x]; hd[x]=st[x]=sz[x]=0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d",&c[i]),f[c[i]]=c[i]; ans+=c[i]!=c[i-1]; if(!hd[c[i]]) st[c[i]]=i; ++sz[c[i]],nxt[i]=hd[c[i]],hd[c[i]]=i; } while(m--) { int opt; scanf("%d",&opt); if(opt==2) printf("%d\n",ans); else { int x,y; scanf("%d%d",&x,&y); if(x==y) continue; if(sz[f[x]]>sz[f[y]]) std::swap(f[x],f[y]); if(!sz[f[x]]) continue; merge(f[x],f[y]); } } return 0; }
- 1
信息
- ID
- 2137
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 12
- 已通过
- 3
- 上传者