题解 P3201 【[HNOI2009]梦幻布丁】

qwaszx · 2019-02-12 13:48:42 · 题解

如果没有修改，那么直接扫一遍，看有多少个位置满足color[i]\neq color[i-1]即可.

有了修改，那么我们就考虑暴力修改

如果要把颜色x都变成y，那么我们先把所有颜色是x的位置找到，然后把它们变成y，同时更新答案.这个找位置的过程可以直接用链表做，对每个颜色开一个链表，更新答案的时候看这个位置两边有没有y，有就答案--，最后把两个链表合并.

然后我们发现把x变成y和把y变成x对答案没什么区别，只是对后面的修改有关系.这样我们每次找一个更短的更新答案.为了处理对修改的影响，开一个数组f[x]表示颜色x所在的链表的颜色即可.

复杂度看起来就是个暴力，但是注意每次合并至少会把一个颜色的规模翻倍，所以每个点最多被处理O(\log n)次,总共O(n\log n).

即启发式合并.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1500000;
int ans[N],size[N],tmp[N],fst[N],nxt[N],f[N],s,n,m,a[N];
void debug(){cout<<233<<endl;}
void merge(int &x,int &y)
{
    if(size[x]>size[y])swap(x,y);//交换
    if(!size[x]||x==y)return;
    for(int i=fst[x];i!=-1;i=nxt[i])
        s-=(a[i-1]==y)+(a[i+1]==y);//更新答案
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        a[i]=y;//修改
        if(nxt[i]==-1){nxt[i]=fst[y],fst[y]=fst[x];break;}//合并
    }
    size[y]+=size[x],size[x]=0,fst[x]=-1;//合并
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<N;i++)fst[i]=-1,f[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);int x=a[i];
        nxt[i]=fst[x],fst[x]=i,size[x]++;//前向星
        if(nxt[i]!=i-1)s++;
    }
    for(int i=1;i<=m;i++)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if(opt==2)printf("%d\n",s);
        else scanf("%d%d",&x,&y),merge(f[x],f[y]);
    }
}