← 返回题目列表

AtCoder · abc391_c

E. 鸽巢查询

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

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