AT_abc329_f [ABC329F] Colored Ball

题目描述

有 $N$ 个编号为 $1, 2, \ldots, N$ 的箱子，最开始第 $i$ 个箱子里有一个颜色为 $C_i$ 的球。

现在给出 $Q$ 个查询，请依次处理这些查询。

每个查询由整数对 $(a, b)$ 给出，具体内容如下：

• 将箱子 $a$ 中的所有球全部移到箱子 $b$ 中，然后输出箱子 $b$ 中现在有多少种颜色的球。

注意，箱子 $a$ 或箱子 $b$ 可能为空。

输入格式

输入以如下格式从标准输入给出。这里，$\text{query}_i$ 表示第 $i$ 个查询。

$N$ $Q$ $C_1$ $C_2$ $\ldots$ $C_N$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

每个查询的格式如下：

$a$ $b$

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

1
2
1
1
3

输入输出样例 #2

输入 #2

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

输出 #2

1
2
0

说明/提示

数据范围

• $1 \leq N, Q \leq 200000$
• $1 \leq C_i \leq N$
• $1 \leq a, b \leq N$
• $a \neq b$
• 输入的所有数值均为整数

样例解释 1

• 第 $1$ 个查询，将箱子 $1$ 的所有球移到箱子 $2$。此时箱子 $2$ 有 $2$ 个颜色为 $1$ 的球，因此输出 $1$。
• 第 $2$ 个查询，将箱子 $6$ 的所有球移到箱子 $4$。此时箱子 $4$ 有 $1$ 个颜色为 $2$ 的球和 $1$ 个颜色为 $3$ 的球，因此输出 $2$。
• 第 $3$ 个查询，将箱子 $5$ 的所有球移到箱子 $1$。此时箱子 $1$ 有 $1$ 个颜色为 $2$ 的球，因此输出 $1$。
• 第 $4$ 个查询，将箱子 $3$ 的所有球移到箱子 $6$。此时箱子 $6$ 有 $1$ 个颜色为 $1$ 的球，因此输出 $1$。
• 第 $5$ 个查询，将箱子 $4$ 的所有球移到箱子 $6$。此时箱子 $6$ 有 $1$ 个颜色为 $1$ 的球、$1$ 个颜色为 $2$ 的球、$1$ 个颜色为 $3$ 的球，因此输出 $3$。

由 ChatGPT 4.1 翻译