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$ 个查询的响应。

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

1
2
1
1
3

5 3
2 4 2 4 2
3 1
2 5
3 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$ 中的所有球移到盒子 $2$。盒子 $2$ 现在包含两颗颜色为 $1$ 的球，因此输出 $1$。

对于第二个查询，将盒子 $6$ 中的所有球移到盒子 $4$。盒子 $4$ 现在包含一颗颜色为 $2$ 的球和一颗颜色为 $3$ 的球，因此输出 $2$。

对于第三个查询，将盒子 $5$ 中的所有球移到盒子 $1$。盒子 $1$ 现在包含一颗颜色为 $2$ 的球，因此输出 $1$。

对于第四个查询，将盒子 $3$ 中的所有球移到盒子 $6$。盒子 $6$ 现在包含一颗颜色为 $1$ 的球，因此输出 $1$。

对于第五个查询，将盒子 $4$ 中的所有球移到盒子 $6$。盒子 $6$ 现在包含一颗颜色为 $1$、一颗颜色为 $2$ 和一颗颜色为 $3$ 的球，因此输出 $3$。

标签: AtCoder|abc329F

来源

AtCoder|abc329F