学步园

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}
int n, m, ans, c[maxn], ft[maxn], head[maxn], size[maxn], end[maxn], next[maxn];

inline void solve(int a, int b) {
    for (int i = head[a]; i; i = next[i]) {
        if (c[i + 1] == b)ans--;
        if (c[i - 1] == b)ans--;
    }
    for (int i = head[a]; i; i = next[i])
        c[i] = b;
    next[end[a]] = head[b];
    size[b] += size[a];
    head[b] = head[a];
    head[a] = size[a] = end[a] = 0;
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        c[i] = read();
        ft[c[i]] = c[i];
        if (c[i] != c[i - 1])ans++;
        if (!head[c[i]])end[c[i]] = i;
        size[c[i]]++;
        next[i] = head[c[i]];
        head[c[i]] = i;
    }
    for (int i = 1; i <= m; i++) {
        int opr = read();
        if (opr == 1) {
            int a = read(), b = read();
            if (a == b)continue;
            if (size[ft[a]] > size[ft[b]])
                swap(ft[a], ft[b]);
            a = ft[a];
            b = ft[b];
            if (size[a] == 0)continue;
            solve(a, b);

        } else printf("%d\n", ans);
    }
    return 0;
}