题目链接:https://vjudge.net/problem/134273/origin
题目大意
中文题目，不过多解释了
题目分析
启发式合并，据说模拟
两个数据结构合并的过程中用容量小的
去加入容量大的的话可以把复杂度降低为nlogn.
对于这道题，我们维护以颜色为标记的链表，用vector存储各个相同颜色的下标，
并且映射关系逻辑要理清楚，
因为我们通过启发式合并可能把颜色归类成了不符合答案的情况，
这时候要添加层映射，然后通过swap两个下标的fa映射关系来
实现最后的合并情况。
然后还有些额外的细节，数据中可能是两个输入值是一样的情况，还有空集的情况。具体时间复杂度分析：
1:每次O(N)
2：每次合并后，队列长度一定大于等于原来短的长度的两倍。
这样相当于每次合并都会让短的长度扩大一倍以上，
最多扩大logN次，所以总复杂度O(NlogN)，每次O(logN)
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e6+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
中文题目，不过多解释了题目分析：
启发式合并，据说模拟
两个数据结构合并的过程中用容量小的
去加入容量大的的话可以把复杂度降低为nlogn.
对于这道题，我们维护以颜色为标记的链表，用vector存储各个相同颜色的下标，
并且映射关系逻辑要理清楚，
因为我们通过启发式合并可能把颜色归类成了不符合答案的情况，
这时候要添加层映射，然后通过swap两个下标的fa映射关系来
实现最后的合并情况。
然后还有些额外的细节，数据中可能是两个输入值是一样的情况，还有空集的情况。具体时间复杂度分析：
1:每次O(N)
2：每次合并后，队列长度一定大于等于原来短的长度的两倍。
这样相当于每次合并都会让短的长度扩大一倍以上，
最多扩大logN次，所以总复杂度O(NlogN)，每次O(logN)
*/
int n,m,a[maxn],ans=1;
int x,y,z,fa[maxn];
vector<int> g[maxn];
int main(){scanf("%d%d",&n,&m);rep(i,1,n+1){scanf("%d",&a[i]);fa[a[i]]=a[i];g[a[i]].push_back(i);if(i>1&&a[i]!=a[i-1]) ans++;}rep(i,0,m){scanf("%d",&x);if(x==2) printf("%d\n",ans);else{scanf("%d%d",&x,&y);if(x==y) continue;if(g[fa[x]].size()>g[fa[y]].size()) swap(fa[x],fa[y]);if(g[fa[x]].size()==0) continue;x=fa[x],y=fa[y];rep(j,0,g[x].size()){g[y].push_back(g[x][j]);if(a[g[x][j]-1]==y) ans--;if(a[g[x][j]+1]==y) ans--;}rep(j,0,g[x].size()) a[g[x][j]]=y;///g[x].clear();///}}return 0;
}