链表启发式合并
每次将元素少的并到多的上面
注意维护一下每个链表维护的真实颜色就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1500005;
int n,m,a[N],siz[N],f[N],ans;
struct Line{
int pos;
Line *next;
Line(){}
Line(int x,Line *y){pos=x;next=y;}
}*color[N];
void Add(int x,int pos){Line *tp=new Line(pos,color[x]);color[x]=tp;}
void Merge(int x,int y){
if(x==y)return;
if(siz[f[x]]>siz[f[y]])swap(f[x],f[y]);
x=f[x];y=f[y];
if(!color[x])return;
for(Line *i=color[x];i;i=i->next){if(a[i->pos-1]==y)ans--;if(a[i->pos+1]==y)ans--;}
for(Line *i=color[x];i;i=i->next)a[i->pos]=y;
Line *Tp;
for(Tp=color[x];Tp->next;Tp=Tp->next);
Tp->next=color[y];color[y]=color[x];color[x]=NULL;
siz[y]+=siz[x];siz[x]=0;
}
int main(){
freopen("1483.in","r",stdin);
freopen("1483.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[a[i]]=a[i];siz[a[i]]++;Add(a[i],i);if(a[i]!=a[i-1])ans++;}
for(int i=1;i<=m;i++){
int opt,x,y;
scanf("%d",&opt);
if(opt==1){scanf("%d %d",&x,&y);Merge(x,y);}
if(opt==2)printf("%d\n",ans);
}
return 0;
}
评论 (0)
