题面：[HNOI2009] 梦幻布丁

题目描述

$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。

例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色.

输入格式

第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。
接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型：

  • 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。
  • 若 $op = 2$，则表示一次询问。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
5
4 3
1 2 2 1
2
1 2 1
2

样例输出 #1

1
2
3
1

提示

样例 1 解释

初始时布丁颜色依次为 $1, 2, 2, 1$，三段颜色分别为 $[1, 1], [2, 3], [4, 4]$。
一次操作后，布丁的颜色变为 $1, 1, 1, 1$，只有 $[1, 4]$ 一段颜色。

数据规模与约定

对于全部的测试点，保证 $1 \leq n, m \leq 10^5$，$1 \leq a_i ,x, y \leq 10^6$。

提示

请注意，不保证颜色的编号不大于 $n$，也不保证 $x \neq y$，$m$ 不是颜色的编号上限。

思路

题目这样层层合并的方式自然而然的想到了启发式合并。问题是如何统计答案，如何合并。我们开一个 vector 存储每个颜色的位置，然后就是按照启发式合并去合并。设当前的位置是 $p$ 那么一次修改对于答案的贡献就是 $(a[p-1] == y)+(a[p+1]==y)$ 然后再合并，再修改原数组。这个答案贡献的意思就是，当前这个点和前面和后面是否同色，有一个同色就会减少一段，两个同色相当于把他们都连了起来，段数减少二。

代码

由于洛谷增加了 hack 数据，所以现在应该是得用链表才能过了，用 vector 会 MLE。

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
inline void Work() {
    int op, x, y;
    while(m--) {
        read(op);
        if(op == 1) {
            read(x, y);
            if(x == y) continue;
            int flag = 0;
            if(pos[x].size() > pos[y].size()) {
                swap(id[x], id[y]); flag = 1;
            }
            x = id[x], y = id[y];
            if(pos[x].size() == 0) continue;
            for(auto &p : pos[x]) {
                ans -= (a[p - 1] == y) + (a[p + 1] == y);
            }
            for(auto &p : pos[x]) {
                pos[y].push_back(p);
                a[p] = y;
            }
            pos[x].clear();
        }
        else {
            printf("%d\n", ans);
        }
    }
}