AT_abc391_c [ABC391C] Pigeonhole Query
题目描述
有 n 只鸽子,编号为 1 至 n。另有 n 个鸽巢,编号为 1 至 n。初始时,鸽子 i(1≦i≦n) 位于巢 i 中。
请依次处理 q 个查询。查询有两种类型:
∙类型 1 查询:给定整数 p 和 h,将鸽子 p 移动到巢 h;
∙类型 2 查询:输出当前包含多只鸽子的鸽巢数量。
输入格式
第一行输入两个整数 $n, q \left(2 \leqq n \leqq 10^6;\ 1 \leqq q \leqq 3 \times 10^5\right)$ 代表鸽子和鸽巢的数量,以及查询的数量。
此后 q 行,第 i 行描述第 i 个查询,格式为以下两种之一:
∙若为类型 1 查询,输入三个整数 1,p,h(1≦p,h≦n),表示将鸽子 p 移动到巢 h,其中移动前鸽子 p 不在巢 h 中;
∙若为类型 2 查询,输入一个整数 2。
输出格式
对于每个类型 2 的查询,新起一行,输出一个整数,代表当前包含多只鸽子的鸽巢数量。所有类型 2 查询的答案按查询出现的顺序输出。
测试样例
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 解释
初始时,鸽子 1,2,3,4 分别位于巢 1,2,3,4。
1.第 1 个查询:巢 1,2,3,4 中分别有 1,1,1,1 只鸽子。没有包含多只鸽子的巢,输出 0;
2.第 2 个查询:将鸽子 1 移动到巢 2;
3.第 3 个查询:巢 1,2,3,4 中分别有 0,2,1,1 只鸽子。包含多只鸽子的巢为巢 2,输出 1;
4.第 4 个查询:将鸽子 3 移动到巢 2;
5.第 5 个查询:巢 1,2,3,4 中分别有 0,3,0,1 只鸽子。包含多只鸽子的巢为巢 2,输出 1;
6.第 6 个查询:将鸽子 3 移动到巢 4;
7.第 7 个查询:巢 1,2,3,4 中分别有 0,2,0,2 只鸽子。包含多只鸽子的巢为巢 2 和巢 4,输出 2。