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

· · 题解

\Large\texttt{My Blog}

题目链接：BZOJ 1483

有 n 个布丁摆成一行，每个布丁都有一个颜色 a_i，进行 m 次操作。操作共有 2 种：

数据范围：1\leqslant n,m\leqslant 10^5，0<a_i,x,y<10^6

Solution

我们可以把每种颜色的布丁集合想象成是一个队列。那么就有若干个长度总和为 n 的队列，每次操作需要合并 x 和 y。如果我们暴力合并，那么合并一次复杂度最坏为 O(n)。

但是有个叫做启发式合并的东西！它的本质很简单：每次把短的合并到长的上面，那么合并一次的复杂度为 O(|短的队列|)。这样看上去貌似没有什么差别嘛 QAQ，接下来我们分析一下均摊复杂度。

考虑用贡献法来分析。我们令两个集合的分别为 A 和 B，且 |A|<|B|，那么我们把 A 暴力加入到 B 中。那么 A 中的元素所在的集合大小变成 |A|+|B|，也就是说至少变成了原来的两倍。所以每个元素至多被加入 \log n 次，总的复杂度为 O(n\log n)。

对于这道题目，我们先求出原序列的答案，对于每一种颜色都用类似链表的数据结构串起来，并记录下尾节点。每次修改，都根据启发式合并的方法来暴力合并，然后处理一下此次合并对答案的影响（显然答案是不增的）。

但是如果我们把 1 染成 2 并且 |S_1|>|S_2|，那么我们应该把 2 接到 1 的后面。这样会有一个问题：本次修改后这个链的颜色是 1（颜色为 2 的链被删除了），如果接下来修改颜色 2（显然这是合法的），会使得找不到颜色 2 而只能找到颜色 1 了。所以我们需要使用一个 f 数组，表示当我们要寻找颜色 x 时，实际上需要寻找颜色为 f[x] 的链。如果遇到上面这种情况就要交换交换 f[x] 和 f[y]。

时间复杂度：O(n\log n)

Code

#include <iostream>
#include <cstdio>

const int N=1e5+5,M=1e6+5;
int n,m,c[N],sz[M],st[M],f[M],hd[M],nxt[N],ans;

void merge(int x,int y) {
    for(int i=hd[x];i;i=nxt[i]) ans-=(c[i-1]==y)+(c[i+1]==y);
    for(int i=hd[x];i;i=nxt[i]) c[i]=y;
    nxt[st[x]]=hd[y],hd[y]=hd[x],sz[y]+=sz[x];
    hd[x]=st[x]=sz[x]=0;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) {
        scanf("%d",&c[i]),f[c[i]]=c[i];
        ans+=c[i]!=c[i-1];
        if(!hd[c[i]]) st[c[i]]=i;
        ++sz[c[i]],nxt[i]=hd[c[i]],hd[c[i]]=i;
    }
    while(m--) {
        int opt;
        scanf("%d",&opt);
        if(opt==2) printf("%d\n",ans);
        else {
            int x,y;
            scanf("%d%d",&x,&y);
            if(x==y) continue;
            if(sz[f[x]]>sz[f[y]]) std::swap(f[x],f[y]);
            if(!sz[f[x]]) continue;
            merge(f[x],f[y]);
        }
    }
    return 0;
}