[HNOI 2009] 梦幻布丁

题目大意

给定一个颜色序列 {ci}\{c_i\},有 mm 次操作,每次操作要么把一种颜色全部改为另一种颜色,要么询问一共有几段颜色。

1n,  m100,0001 \leqslant n, \; m \leqslant 100,000

1ci1,000,0001 \leqslant c_i \leqslant 1,000,000

题目链接

【HNOI 2009】梦幻布丁

题解

链表 + 启发式合并。

为每个颜色开一个链表,每次修改操作即为合并两个链表并更新答案。更新时暴力沿着颜色对应的链表走一遍,看两侧的颜色是不是被修改成的颜色,若是,则答案减 11,可是这样最坏要更新 nn 个点。

考虑启发式合并,把小的合并到大的上面,每次链表长度至少变长一倍,最多变长 O(logn)O(\log n) 次,总复杂度变为了 O(mlogn)O(m \log n)

当要被修改的颜色为更多的一方时,交换要修改成的颜色和要被修改的颜色,同时用一个数组记录一个颜色目前由哪个链表保存。(比如把 aa 修改成 bb,但 aabb 多,那处理后 aa 的链表来保存颜色bb的点)

代码

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
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <algorithm>
const int MAXN = 100005;
const int MAXC = 1000005;
int next[MAXN], a[MAXM];
int size[MAXC], first[MAXC], last[MAXC], find[MAXC];
int ans;
void merge(int x, int y) {
if (size[x] == 0) return;
for (int i = last[x]; i; i = next[i]) {
if (a[i - 1] == y) ans--;
if (a[i + 1] == y) ans--;
}
for (int i = last[x]; i; i = next[i]) a[i] = y;
next[first[x]] = last[y];
last[y] = last[x];
size[y] += size[x];
size[x] = first[x] = last[x] = 0;
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
find[a[i]] = a[i];
if (a[i] != a[i - 1]) ans++;
if (!first[a[i]]) first[a[i]] = i;
next[i] = last[a[i]];
last[a[i]] = i;
size[a[i]]++;
}
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
int x, y;
scanf("%d %d", &x, &y);
if (x == y) continue;
if (size[find[x]] > size[find[y]]) std::swap(find[x], find[y]);
x = find[x], y = find[y];
merge(x, y);
} else printf("%d\n", ans);
}
return 0;
}