套路题

我们对每一个颜色开一个队列，一开始的答案很显然可以\(O(n)\)得到，那么我们每改一个地方从\(x\)变为\(y\)的话，看一看这个位置前后是不是为\(y\)，如果是的话，初始答案\(-1\)

并且，每一次修改相当于合并两个队列，那就想到启发式合并了，那么其实把\(x\)变成\(y\)，把\(y\)变成\(x\)其实是一样的，只不过对后面的修改操作有影响

那么我们用\(col[i]\)数组表示现在是\(i\)这个颜色的链表原来是什么颜色

接下来是美滋滋的代码时间~~~

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 1500007
using namespace std;
int n,m,ans;
int a[N],col[N],siz[N],head[N],nxt[N];
void Merge(int &x,int &y)
{
    if(siz[x]>siz[y])
        swap(x,y);
    if(!siz[x]||x==y)
        return;
    for(int i=head[x];i!=-1;i=nxt[i])
        ans-=(a[i-1]==y)+(a[i+1]==y);
    for(int i=head[x];i!=-1;i=nxt[i])
    {
        a[i]=y;
        if(nxt[i]==-1)
        {
            nxt[i]=head[y];
            head[y]=head[x];
            break;
        }
    }
    siz[y]+=siz[x];
    siz[x]=0;
    head[x]=0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=N-7;++i)
        head[i]=-1,col[i]=i;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        nxt[i]=head[a[i]];
        head[a[i]]=i;
        ++siz[a[i]];
        if(a[i-1]!=a[i])
            ++ans;
    }
    for(int i=1;i<=m;++i)
    {
        int opt,x,y;
        scanf("%d",&opt);
        if(opt==2)
            printf("%d\n",ans);
        else
        {
            scanf("%d%d",&x,&y);
            Merge(col[x],col[y]);
        }
    }
    return 0;
}

[HNOI2009]梦幻布丁

原文：https://www.cnblogs.com/yexinqwq/p/11167085.html