我们用color映射每个位置所代表的颜色。
用p[x]表示当前颜色为x的位置为y，这是因为颜色合并的时候，将小集合合并到大集合。
那么，颜色的合并就会改变。比如将1变为2，但是2的集合小于1，实际情况是将2集合合并到集合1
那么，我们就将p[x]和p[y]交换一下。相当于颜色的实际指向，类似于指针
ans表示集合个数
将相同颜色存放在同一个链表，方便修改颜色，用sz表示当前颜色的个数，也就是颜色集合的大小，
是在合并集合的时候用的。
对于颜色修改：x修改为y
如果颜色相同就不修改。
如果x集合大于y，按照启发式合并的原理，应该将y合并到x。
所以我们交换x和y，同时修改p这个指针的颜色指向，可以用引用地址来解决。
通过链表查询x的所有位置，如果他的左边有y，那么总集合数-1，如果右边有y，总集合数再-1
在遍历集合x的时候，将颜色x的所有位置j的颜色color修改成y
当遍历到末尾的时候，修改指针指向，将链表y存放到x中去

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 1000005;
int n,m;
int h[M], e[N], ne[N], idx;
int color[N], sz[M], p[M];
int ans;
void add(int a, int b)
{
  e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
//地址引用，要是修改的话，直接将p指向的方向也改了
void merge(int& x, int& y)
{
  if (x == y) return;
  //按照启发式合并的原理，小集合合并到大集合
  if (sz[x] > sz[y]) swap(x, y);
  //将x全部修改为y
  for (int i = h[x]; ~i; i = ne[i])
  {
    //如果颜色x出现的位置，周围有颜色y，那么分段必会减少
    int j = e[i];
    ans -= (color[j - 1] == y) + (color[j + 1] == y);
  }
  for (int i = h[x]; ~i; i = ne[i])
  {
    //将颜色x集合内的所有元素的颜色都修改成y
    int j = e[i];
    color[j] = y;
    if (ne[i] == -1)
    {
      //到修改到了x集合的尾元素，ne指针指向y的头指针指向的位置
      //然后，将头指针的指向，指向x头指针指向的位置，
      //然后，x串没了，h[x] = -1，表示不指向任何位置
      //将x集合元素个数加到y集合，x集合元素为0
      ne[i] = h[y], h[y] = h[x], h[x] = -1, sz[y] += sz[x], sz[x] = 0;
      break;
    }
  }
}
int main()
{
  memset(h, -1, sizeof h);
  for (int i = 1; i < M; i ++ ) p[i] = i;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i ++ )
  {
    scanf("%d", &color[i]);
    add(color[i], i);
    if (color[i] != color[i - 1]) ans ++;
  }
  while (m -- )
  {
    int op; scanf("%d", &op);
    if (op == 2) printf("%d\n", ans);
    else
    {
      int x, y; scanf("%d%d", &x, &y);
      merge(p[x], p[y]);
    }
  }
  return 0;
}