梦幻布丁「HNOI2009」

题意

给定一个有多种颜色组成的序列，以及两种操作：

1. 将某种颜色全部染成另一种颜色。

2. 询问颜色段的数量。

思路

将每一种颜色的位置分别存入链表，然后染色的时候启发式合并。

这道题数据出的比较毒瘤，有同种颜色互相染色的数据，还有将已经不存在的颜色进行染色的数据，需要特判。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
    
    const int N=1000100;
    
    int n,m,ans;
    int a[N];
    int id[N],head[N],next[N],size[N],tail[N];
    
    inline void merge (int x,int y) {
        for (register int i=head[x]; i; i=next[i]) ans-=(a[i-1]==y)+(a[i+1]==y);
        for (register int i=head[x]; i; i=next[i]) a[i]=y;
        size[y]+=size[x],next[tail[x]]=head[y],head[y]=head[x];
        size[x]=head[x]=tail[x]=0;
    }

    inline void MAIN () {
        read(n),read(m);
        for (register int i=1; i<=n; ++i) {
            read(a[i]),id[a[i]]=a[i];
            ans+=a[i]!=a[i-1];
            if (!head[a[i]]) tail[a[i]]=i;
            ++size[a[i]],next[i]=head[a[i]],head[a[i]]=i;
        }
        while (m--) {
            int op,x,y;
            read(op);
            if (op==1) {
                read(x),read(y);
                if (x==y) continue;
                if (size[id[x]]>size[id[y]]) swap(id[x],id[y]);
                if (!size[id[x]]) continue;
                merge(id[x],id[y]);
            } else {
                write(ans),putchar('\n');
            }
        }
    }
    
}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Project::MAIN();
}

梦幻布丁「HNOI2009」

原文：https://www.cnblogs.com/ilverene/p/11483397.html