BZOJ1483 [HNOI2009]梦幻布丁 【链表 + 启发式合并】

题目

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.

例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

输入格式

第一行给出N,M表示布丁的个数和好友的操作次数.

第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,

对于每个操作,

若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y.

若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. 0。

n,m<=1000000

输出格式

针对第二类操作即询问，依次输出当前有多少段颜色.

输入样例

4 3

1 2 2 1

2

1 2 1

2

输出样例

3

1

题解

QAQ链表还是写不好，照别人的写了好久

【照这种水平一个月后区去清华体验营怎么混QAQ】

我们用链表存每种颜色的位置，然后启发式合并【就是小的并到大的里边】

由于我们可能会交换颜色合并的方向，所以有时候一种颜色的头指针可能并不代表它自己，我们需要用一个数组f[]来储存一下每种颜色对应的头指针

合并的时候，对被合并的颜色的每一个位置，如果旁边就是合并到的颜色，ans–

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

using namespace std;

const int maxn = 1000005,maxm = 100005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int A[maxn],h[maxn],nxt[maxn],siz[maxn],f[maxn],sz = 0,ans = 0,N,M;

void insert(int c){nxt[++sz] = h[c]; h[c] = sz;}

void merge(int x,int y){

    if (x == y) return;

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

    x = f[x]; y = f[y];

    int k;

    if (!h[x]) return;

    for (k = h[x]; k; k = nxt[k])

        ans -= (A[k - 1] == y) + (A[k + 1] == y);

    for (k = h[x]; k; k = nxt[k]) A[k] = y;

    for (k = h[y]; nxt[k]; k = nxt[k]);

    nxt[k] = h[x]; siz[y] += siz[x]; siz[x] = 0; h[x] = 0;

}

int main(){

    N = RD(); M = RD(); int opt,x,y;

    REP(i,N){

        A[i] = RD();

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

        insert(A[i]);

        siz[A[i]]++; f[A[i]] = A[i];

    }

    while (M--){

        opt = RD();

        if (opt == 1) x = RD(),y = RD(),merge(x,y);

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

    }

    return 0;

}