1483: [HNOI2009]梦幻布丁

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=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 1000005;
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 + 1] == y) ans --;
        if (col[i - 1] == 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] = 0;
}
int main() {
    int n = read(), m = read();
    col[0] = -1;
    for (int i = 1; i <= n; ++i) {
        col[i] = read();
        if (col[i] != col[i - 1]) 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 = 1; i <= m; ++i) {
        int opt = read();
        if (opt == 2) printf("%d
", 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] == 0) continue;
            siz[y] += siz[x]; siz[x] = 0;
            Merge(x, y);
        }
    }
    return 0;
}