Problem

给定$n(n \le 10^6)$个小球，排着一排，每个球都有一种颜色

现在要求维护两种操作：

  1. 将所有颜色为$x$的球变成颜色为$y$的球
  2. 查询这排小球有多少连续相同的色段

Solution

我们维护每种颜色的位置链表

当发生合并时，将$size$小的链表并入$size$大的链表

枚举$x$颜色每个位置，暴力染成$y$，如果和左右节点染色后颜色相同则答案发生修改

并入时$size$翻倍，因此每个点最多并入$log_2n$次，复杂度$O(nlog_2n)$

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
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int N = 1000000 + 10;
int G[N], nxt[N], v[N], cnt = 0;
int id[N], c[N], siz[N];
int n, m, op, x, y, ans;
void merge(int x, int y) {
	if (x == y) return; 
    if (siz[id[x]] > siz[id[y]]) swap(id[x], id[y]);
    x = id[x], y = id[y];
    if (!siz[x]) return;
    siz[y] += siz[x]; siz[x] = 0;
    for (int i = G[x]; i; i = nxt[i]) {
        int u = v[i];
        if (c[u - 1] == y) ans--;
        if (c[u + 1] == y) ans--;
    }
    for (int i = G[x]; i; i = nxt[i]) {
        int u = v[i];
        c[u] = y;
        if (!nxt[i]) {
            nxt[i] = G[y];
            break;
        }
    }
    G[y] = G[x], G[x] = 0;
}
int main() {
    scanf("%d%d", &n, &m);
    ans = n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
        if (c[i] == c[i - 1]) ans--;
        siz[c[i]]++;
        id[c[i]] = c[i];
        v[++cnt] = i;
        nxt[cnt] = G[c[i]];
        G[c[i]] = cnt;
    }
    while (m--) {
        scanf("%d", &op);
        if (op == 2)
            printf("%d\n", ans);
        else {
            scanf("%d%d", &x, &y);
            merge(x, y);
        }
    }
    return 0;
}