分数: 500 点
问题陈述
有 N 盒子编号 1, 2, \ldots, N。最初,盒子 i 包含一个彩色球 C_i.
你被给予 Q 查询,您应按顺序处理。
每个查询由一对整数给出 (a,b) 并要求您执行以下操作:
- 将盒子中的所有球移出 a 到盒子 b,然后打印框中不同颜色球的数量 b.
这里,盒子 a 和 b 可能为空。
约束
- 1 \leq N, Q \leq 200000
- 1 \leq C_i \leq N
- 1 \leq a, b \leq N
- a \neq 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
6 5 1 1 1 2 2 3 1 2 6 4 5 1 3 6 4 6
示例输出 1
1 2 1 1 3
-
对于第一个查询,将盒子中的所有球移出 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.
示例输入 2
5 3 2 4 2 4 2 3 1 2 5 3 2
示例输出 2
1 2 0