BZOJ-1483: [HNOI2009]梦幻布丁

Description

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.N<=10^6

启发式合并链表。
链表的合并方法有两种，第一种是拆了，一个个加到另一个里；
第二种是遍历一个链表，将最后的nxt指向另一个的head
之后对于整体的颜色段数，用链表遍历，修改颜色，对于每一个位置，考虑改颜色的贡献。复杂度nlogn

#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1001000 
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
    return x;
}
int n,m,ans,a[N];
int head[N],siz[N],nxt[N],col[N],cnt;
inline void add(int x,int y) {nxt[y]=head[x]; head[x]=y;}
int main()
{
    n=read(); m=read();
    int i; a[0]=a[n+1]=-1;
    for(i=1;i<=1000000;++i) col[i]=i;
    for(i=1;i<=n;++i)
    {
        a[i]=read(); add(a[i],i);
        siz[a[i]]++; ans+=(a[i]!=a[i-1]);
    }
    int sw,x,y,t;
    while(m--)
    {
        sw=read();
        if(sw==2) printf("%d\n",ans);
        else
        {
            x=read(); y=read();
            if(x!=y)
            {
                if(siz[x]<siz[y])
                {
                    for(i=head[x];i;i=nxt[i])
                    {
                        ans-=(a[i]!=a[i-1]);
                        if(i!=n) ans-=(a[i+1]!=a[i]);
                        a[i]=col[y];
                        ans+=(a[i]!=a[i-1]);
                        if(i!=n) ans+=(a[i+1]!=a[i]);
                    }
                    col[x]=col[y];
                    for(t=0,i=head[x];i;t=i,i=nxt[i]) if(t) add(y,t);
                    if(t) add(y,t);
                }
                else
                {
                    for(i=head[y];i;i=nxt[i])
                    {
                        ans-=(a[i]!=a[i-1]);
                        if(i!=n) ans-=(a[i+1]!=a[i]);
                        a[i]=col[x];
                        ans+=(a[i]!=a[i-1]);
                        if(i!=n) ans+=(a[i+1]!=a[i]);
                    }
                    col[y]=col[x]; int *j;
                    for(j=&head[y];*j;j=&nxt[*j]); *j=head[x];
                }
                siz[y]+=siz[x]; siz[x]=head[x]=0;
            }
        }
    }
    return 0;
}