「HNOI 2009」梦幻布丁

发表于 | | 阅读次数:
字数统计: 823 字

Description

题目链接：BZOJ 1483

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

  • 1 x y：将颜色为 $x$ 的布丁全部变成颜色 $y$ 的布丁。
  • 2：询问当前一共有多少段颜色（例如颜色分别为 $1,2,2,1$ 的 $4$ 个布丁一共有 $3$ 段颜色）。

数据范围：$1\le n,m\le 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#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;
}
0%