链表+启发式合并
懒得写链表
std::set代替链表
首先算出初始状态答案
然后对于每个修改操作，启发式合并两种颜色。
启发式合并：在合并两个集合（或两棵树）时，暴力将较小集合的元素（或结点更少的树的所有节点）合并（或插入）到另一较大集合（或结点更多的树）中。
简单来说就是弱肉强食。
而且启发式合并的时间复杂度可以证明是O(logn)的
对于本题，枚举较小的集合的每个元素，处理答案并且加入较大的集合，同时更改颜色。
对于查询操作，由于每次修改同时都计算出答案，直接输出即可。
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cctype>
#include <set>
#include <algorithm>
const int N = 1000000 + 10;
int a[N], f[N];
std::set <int> c[N];
int read(void);
int main(void)
{
int n = read(), m = read();
for (int i = 1; i <= n; ++i)
a[i] = read();
int ans = 0;
for (int i = 1; i <= n; ++i)
{
f[a[i]] = a[i];
c[a[i]].insert(i);
if (a[i] != a[i - 1])
++ans;
}
while (m--)
{
int op = read();
if (op == 1)
{
int x = read(), y = read();
if (x != y)
{
if (c[f[x]].size() > c[f[y]].size())
std::swap(f[x], f[y]);
x = f[x];
y = f[y];
for (std::set <int> ::iterator i = c[x].begin(); i != c[x].end(); ++i)
ans -= (y == a[*i - 1]) + (y == a[*i + 1]);
for (std::set <int> ::iterator i = c[x].begin(); i != c[x].end(); ++i)
{
a[*i] = y;
c[y].insert(*i);
}
c[x].clear();
}
}
else
printf("%d\n", ans);
}
return 0;
}
inline int read(void)
{
char x;
while (!isdigit(x = getchar()))
;
int num = x - '0';
while (isdigit(x = getchar()))
(num *= 10) += x - '0';
return num;
}