传送门

名字起得很高端实际上很简单的算法hhh

启发式合并

简单讲就是一些合并一堆队列的题可以用启发式合并，或者说这是一个思想。每次把小的合并到大的部分，均摊复杂度$O(MlogN)$。

//BZOJ 1483//by Cydiater//2016.10.25#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <bitset>#include <cstring>#include <string>#include <algorithm>#include <cstdio>#include <iomanip>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,realc[MAXN],a[MAXN],next[MAXN],head[MAXN],nd[MAXN],siz[MAXN],ans=0,M;namespace solution{	void init(){		N=read();M=read();		up(i,1,N){			a[i]=read();siz[a[i]]++;			if(a[i]!=a[i-1])ans++;			if(!nd[a[i]])nd[a[i]]=i;			next[i]=head[a[i]];head[a[i]]=i;			realc[a[i]]=a[i];		}	}	void updata(int x,int y){		if(x==y)return;		if(siz[realc[x]]>siz[realc[y]])swap(realc[x],realc[y]);		x=realc[x];y=realc[y];		if(siz[x]==0)return;		for(int i=head[x];i;i=next[i]){			if(a[i+1]==y)ans--;			if(a[i-1]==y)ans--;		}		for(int i=head[x];i;i=next[i])a[i]=y;		siz[y]+=siz[x];next[nd[y]]=head[x];nd[y]=nd[x];		head[x]=nd[x]=siz[x]=0;	}	void slove(){		while(M--){			int opt=read(),x,y;			if(opt==2)printf("%d\n",ans);			else{				x=read();y=read();				updata(x,y);			}		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove();	return 0;}

BZOJ1483: [HNOI2009]梦幻布丁