思路：将颜色相同的建成一个链表， 变颜色的时候进行链表的启发式合并。。

因为需要将小的接到大的上边，所以要用个f数组。

#include
     
      #define LL long long#define fi first#define se second#define mk make_pair#define pii pair
      
       using namespace std;const int N = 1e6 + 7;const int M = 1e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 +7;int n, m, ans, f[N], a[N];struct node {    node(int id, node *nx) {        this->id = id;        this->nx = nx;    }    int id;    node *nx;} *head[N];void Insert(int x, int id) {    node *p = new node(id, head[x]->nx);    head[x]->nx = p;    head[x]->id++;}void Merge(int x, int y) {    if(x == y) return;    if(head[f[x]]->id > head[f[y]]->id) swap(f[x], f[y]);    x = f[x], y = f[y];    node *cur =  head[x];    while(cur -> nx != NULL) {        cur = cur -> nx;        int id = cur->id;        if(a[id - 1] == y) ans--;        if(a[id + 1] == y) ans--;    }    cur = head[x];    while(cur -> nx != NULL) {        cur = cur -> nx;        int id = cur -> id;        a[id] = y;    }    cur = head[y];    while(cur -> nx != NULL) {        cur = cur -> nx;    }    cur->nx = head[x]->nx;    head[y]->id += head[x]->id;    head[x]->id = 0;    head[x]->nx = NULL;}int main() {    for(int i = 1; i <= 1e6; i++) {        f[i] = i;        head[i] = new node(0, NULL);    }    scanf("%d%d", &n, &m);    for(int i = 1; i <= n; i++) {        scanf("%d", &a[i]);        if(a[i] != a[i - 1]) ans++;        Insert(a[i], i);    }    while(m--) {        int op; scanf("%d", &op);        if(op == 1) {            int x, y; scanf("%d%d", &x, &y);            Merge(x, y);        } else {            printf("%d\n", ans);        }    }    return 0;}/**/