#ABC391C. 鸽巢询问

鸽巢询问

AT_abc391_c [ABC391C] Pigeonhole Query

题目描述

\hspace{15pt}有 nn 只鸽子,编号为 11 至 nn。另有 nn 个鸽巢,编号为 11 至 nn。初始时,鸽子 i(1≦i≦n)i \left(1 \leqq i \leqq n\right) 位于巢 ii 中。

\hspace{15pt}请依次处理 qq 个查询。查询有两种类型:

∙ \hspace{23pt}\bullet\,类型 11 查询:给定整数 pp 和 hh,将鸽子 pp 移动到巢 hh;

∙ \hspace{23pt}\bullet\,类型 22 查询:输出当前包含多只鸽子的鸽巢数量。

输入格式

\hspace{15pt}第一行输入两个整数 $n, q \left(2 \leqq n \leqq 10^6;\ 1 \leqq q \leqq 3 \times 10^5\right)$ 代表鸽子和鸽巢的数量,以及查询的数量。

\hspace{15pt}此后 qq 行,第 ii 行描述第 ii 个查询,格式为以下两种之一:

∙ \hspace{23pt}\bullet\,若为类型 11 查询,输入三个整数 1,p,h(1≦p,h≦n)1, p, h \left(1 \leqq p, h \leqq n\right),表示将鸽子 pp 移动到巢 hh,其中移动前鸽子 pp 不在巢 hh 中;

∙ \hspace{23pt}\bullet\,若为类型 22 查询,输入一个整数 22。

输出格式

\hspace{15pt}对于每个类型 22 的查询,新起一行,输出一个整数,代表当前包含多只鸽子的鸽巢数量。所有类型 22 查询的答案按查询出现的顺序输出。

测试样例

4 7
2
1 1 2
2
1 3 2
2
1 3 4
2
0
1
1
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
0
1
2
1

样例 1 解释

\hspace{15pt}初始时,鸽子 1,2,3,41, 2, 3, 4 分别位于巢 1,2,3,41, 2, 3, 4。

1. {\hspace{20pt}}_\texttt{1.}\,第 11 个查询:巢 1,2,3,41, 2, 3, 4 中分别有 1,1,1,11, 1, 1, 1 只鸽子。没有包含多只鸽子的巢,输出 00;

2. {\hspace{20pt}}_\texttt{2.}\,第 22 个查询:将鸽子 11 移动到巢 22;

3. {\hspace{20pt}}_\texttt{3.}\,第 33 个查询:巢 1,2,3,41, 2, 3, 4 中分别有 0,2,1,10, 2, 1, 1 只鸽子。包含多只鸽子的巢为巢 22,输出 11;

4. {\hspace{20pt}}_\texttt{4.}\,第 44 个查询:将鸽子 33 移动到巢 22;

5. {\hspace{20pt}}_\texttt{5.}\,第 55 个查询:巢 1,2,3,41, 2, 3, 4 中分别有 0,3,0,10, 3, 0, 1 只鸽子。包含多只鸽子的巢为巢 22,输出 11;

6. {\hspace{20pt}}_\texttt{6.}\,第 66 个查询:将鸽子 33 移动到巢 44;

7. {\hspace{20pt}}_\texttt{7.}\,第 77 个查询:巢 1,2,3,41, 2, 3, 4 中分别有 0,2,0,20, 2, 0, 2 只鸽子。包含多只鸽子的巢为巢 22 和巢 44,输出 22。