1483: [HNOI2009]梦幻布丁

链接

分析：

　　启发式合并+链表。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int head[N], nxt[N], siz[N], pos[N], col[N], fir[N], ans;

void Merge(int x,int y) {

    for (int i = head[x]; i; i = nxt[i]) {

        if (col[i + ] == y) ans --;

        if (col[i - ] == y) ans --;

    }

    for (int i = head[x]; i; i = nxt[i]) col[i] = y;

    nxt[fir[x]] = head[y], head[y] = head[x];

    siz[x] = head[x] = ;

}

int main() {

    int n = read(), m = read();

    col[] = -;

    for (int i = ; i <= n; ++i) {

        col[i] = read();

        if (col[i] != col[i - ]) ans ++;

        if (!pos[col[i]]) pos[col[i]] = col[i];

        if (!head[col[i]]) fir[col[i]] = i;

        siz[col[i]] ++, nxt[i] = head[col[i]], head[col[i]] = i;

    }

    for (int i = ; i <= m; ++i) {

        int opt = read();

        if (opt == ) printf("%d\n", ans);

        else {

            int x = read(), y = read();

            if (x == y) continue;

            if (siz[pos[x]] > siz[pos[y]]) swap(pos[x], pos[y]);

            x = pos[x], y = pos[y];

            if (siz[x] == ) continue;

            siz[y] += siz[x]; siz[x] = ;

            Merge(x, y);

        }

    }

    return ;

}