分数: 300 点
问题陈述
有 N 鸽子编号为 1 to N,并且有 N 巢穴编号自 1 to N。最初,鸽子 i 在巢中 i 为 1\leq i\leq N.
你被给予 Q 查询,您必须按顺序处理。有两种类型的查询,每种查询都以以下格式之一给出:
1 P H: 移动鸽子 P 筑巢 H.2:输出包含多于一只鸽子的巢的数量。
约束
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 3\times 10^5
- 1 \leq P, H \leq N
- 对于第一类查询,piging P 不在巢中 H 移动之前。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询均以以下两种格式之一给出:
1 P H
2
输出
根据问题陈述中的说明,在新行上打印每个查询的答案。
示例输入 1
4 7 2 1 1 2 2 1 3 2 2 1 3 4 2
示例输出 1
0 1 1 2
最初,鸽子 1,2,3,4 在巢中 1,2,3,4。
- 对于第一个查询,巢中鸽子的数量 1,2,3,4 是 1,1,1,1。没有巢穴包含多只鸽子,输出 0.
- 对于第二个查询,移动鸽子 1 筑巢 2.
- 对于第三个查询,计数变为 分别为 0,2,1,1。一窝(一窝 2) 包含多只鸽子,因此输出 1.
- 第四次查询,移鸽子 3 筑巢 2.
- 对于第 5 个查询,计数变为 0,3,0,1。一窝(一窝 2) 包含多只鸽子,因此输出 1.
- 第6次查询,移鸽子 3 筑巢 4.
- 对于第 7 个查询,计数变为 分别是 0,2,0,2。两个巢(巢 2 和 4) 包含多只鸽子,因此输出 2.
示例输入 2
5 10 2 1 4 3 1 4 5 2 1 3 1 2 1 2 3 1 2 5 1 1 3 2
示例输出 2
0 1 2 1