假设现在有\(n\)个元素，每个元素最开始单独成为一个集合
现在有一种合并操作，可以合并两个集合，假设将集合\(A\)合并到集合\(B\)，那么时间复杂度为\(O(|A|p)\)，其中\(O(p)\)表示合并一个元素的操作的复杂度，也就是说我们的操作每次是合并一个元素和一个集合，所以我们将\(A\)合并到\(B\)里，就要对\(A\)中每个元素作合并操作，于是时间复杂度为\(O(|A|p)\)
假设我们依次合并（i.e.先将\(\left\{1\right\}\)合并到\(\left\{2\right\}\)，再将\(\left\{1\space2\right\}\)合并到\(\left\{3\right\}\)，再将\(\left\{1\space2\space 3\right\}\)合并到\(\left\{4\right\}\)，以此类推），那么不难知道时间复杂度为\(O(n^2p)\)
但是我们现在采取一个优化，每次合并都将元素个数少的集合合并到元素个数多的集合里面，这样的话时间复杂度就会变为\(O(n\log np)\)
证明：考虑每个元素对时间复杂度的贡献，为\(O(ap)\)，其中\(a\)是这个元素被合并的次数，而这显然就等于其所在的不同集合的个数；考虑其所在的不同集合一共有多少个，由于每次合并是将小的集合合并到大的集合里面，那么每次小的集合的元素个数至少乘以\(2\)，所以\(a\)的上界为\(O(\log n)\)，于是得证
然后来考虑这道题目。注意，我们的启发式合并每次是合并一个元素的，所以我们应该考虑假设我们每次只改变一个元素的颜色（而不是所有这个元素的颜色一起改变）答案会发生什么变化
比较显然，设\(cnt\)为改变之前的答案，当前将元素\(i\)（\(i\)是下标）的颜色\(x\)改变为\(y\)，那么如果\(i-1\)的颜色为\(y\)，\(cnt\)会减一；如果\(i+1\)的颜色为\(y\)，\(cnt\)会减一
于是我们现在就可以找到一个\(O(n^2)\)的暴力算法了，考虑用启发式合并优化
由于启发式合并会将更小的集合合并到更大的集合，涉及到集合的快速交换，所以我们需要一个散列表h[i]来表示某一种颜色的位置，并且再用一个单独的数组p[i]来表示这个颜色对应的散列表指针（这样在交换集合的时候就可以\(O(1)\)交换p了）。注意h[i]并不是表示颜色\(i\)的位置，只有p[i]才表示颜色\(i\)，p[i]指向的散列表表示\(i\)的位置（p[i]不一定指向h[i]），然后剩下的可以看y总的代码；注意其代码的color数组并不是表示真实的颜色，color[i]!=color[j]只能说明位置\(i,j\)的颜色不同，但是并不表示位置\(i,j\)的颜色分别为color[i]，color[j]，所以交换的操作显然正确，而且交换之后ans显然不变；还要注意merge函数的参数表里面是引用
但是有一种用vector的更简单的写法。设vector<int> g[N]，其中g[i]表示颜色\(i\)的位置，color的意义与y总代码相同；然后利用vecotr的成员函数swap进行高效交换（这个时间复杂度是\(O(1)\)的，原因好像是因为交换的指针）即可，代码见下
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
const ll mod=1e9+7;
int n,m;
int cnt,color[N];
vector<int> g[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&color[i]);
g[color[i]].push_back(i);
cnt+=(color[i]!=color[i-1]);
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y;
scanf("%d%d",&x,&y);
if(x==y) continue;
if(g[x].size()>g[y].size()) g[x].swap(g[y]);
//假设颜色x的数量更多，就要交换
//但是题目要求的是将x变成y不是将y变成x
//所以此时认为，原来是x的位置现在全部变成y，原来是y的位置现在全部变成x
//易知此时cnt不变
//然后再将此时颜色x全部变成颜色y即可
int v=color[g[y].back()];
for(int i=0;i<g[x].size();i++)
cnt-=(color[g[x][i]-1]==v)+(color[g[x][i]+1]==v);
while(g[x].size())
{
color[g[x].back()] = v;
g[y].push_back(g[x].back());
g[x].pop_back();
}
}
else printf("%d\n",cnt);
}
return 0;
}