「HNOI 2009」梦幻布丁

题目大意：

启发式合并链表。

#include <cstdio>

const int N = 100005, M = 1000005;
int c[N], head[M], nxt[N], pos[M], siz[M], fa[M], ans;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void swap(int &x, int &y) {
    x ^= y, y ^= x, x ^= y;
}
void merge(int a, int b) {
    for (int i = head[a]; i; i = nxt[i])
        ans -= (c[i-1] == b) + (c[i+1] == b);
    for (int i = head[a]; i; i = nxt[i])
        c[i] = b;
    nxt[pos[a]] = head[b], head[b] = head[a]; //把a接到b的前面
    siz[b] += siz[a], head[a] = pos[a] = siz[a] = 0;
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        c[i] = read(), fa[c[i]] = c[i];
        if (c[i] != c[i-1]) ++ans;
        if (!head[c[i]]) pos[c[i]] = i; //pos[c[i]]实际上是链表中c[i]的最后一个位置
        ++siz[c[i]], nxt[i] = head[c[i]], head[c[i]] = i;
    }
    while (m--) {
        int opt = read();
        if (opt == 1) {
            int a = read(), b = read();
            if (a == b) continue;
            if (siz[fa[a]] > siz[fa[b]]) swap(fa[a], fa[b]);
            a = fa[a], b = fa[b];
            if (siz[a] == 0) continue;
            merge(a, b);
        } else printf("%d\n", ans);
    }
    return 0;
}