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


原题链接
将每个颜色出现的位置用链表串起来(不用按顺序),将颜色x都变成颜色y时:
1.x比y少:直接把x暴力合上去,顺便维护一波答案.
2.x比y多:以后拿y表示x,拿x表示y,把y合到x上,维护答案.
这是个启发式合并,所以复杂度是Log的(^o^)/~
有一定的细节,建议先缕清思路再码(╯‵□′)╯︵┻━┻

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1002333
using namespace std;
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 void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,m,maxcol,a[N],head[N],to[N],nxt[N],tot;
int size[N],id[N],ans;
inline void add(int x,int y,int i)
{
    size[x]++;
    to[i]=y;
    nxt[i]=head[x];
    head[x]=i;
}
inline void fix(int pos,int col)
{
    if(pos!=1)ans-=(a[pos]!=a[pos-1]);
    if(pos!=n)ans-=(a[pos]!=a[pos+1]);
    a[pos]=col;
    if(pos!=1)ans+=(a[pos]!=a[pos-1]);
    if(pos!=n)ans+=(a[pos]!=a[pos+1]);
}
inline void merge(int x,int y)
{
    int i,tmp;
    if(size[x]>size[y])
        swap(id[x],id[y]),swap(head[x],head[y]),swap(size[x],size[y]);
    for(i=head[x];i;i=tmp)tmp=nxt[i],fix(to[i],id[y]),add(y,to[i],i);
    head[x]=size[x]=0;
}
int main()
{
    read(n),read(m);
    int i;
    for(i=1;i<=n;++i)
    {
        read(a[i]);
        maxcol=max(maxcol,a[i]);
        add(a[i],i,++tot);
    }
    for(i=1;i<=n;++i)if(a[i]!=a[i-1])ans++;
    for(i=1;i<=maxcol;++i)id[i]=i;
    int flag,x,y;
    for(i=1;i<=m;++i)
    {
        read(flag);
        if(flag==1)
        {
            read(x),read(y);
            if(x!=y)merge(x,y);
        }
        else printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注