← 返回题目列表

AtCoder · abc329_f

I. 彩球

中文机器翻译题面 查看原题

分数: 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