AT_abc183_f [ABC183F] Confluence

题目描述

有 $N$ 名学生准备上学。第 $i$ 名学生属于班级 $C_i$。

每位学生从自己家出发，途中会不断与其他学生汇合，一起前往学校。已经汇合的学生不会再分开。

现在给出 $Q$ 个查询，请按顺序处理。查询有两种类型，输入格式和内容如下：

• 1 a b ：将包含学生 $a$ 的集体与包含学生 $b$ 的集体合并（如果已经在同一集体中则什么都不做）。
• 2 x y ：询问当前与学生 $x$ 已经汇合在一起的所有学生（包括 $x$ 本人）中，属于班级 $y$ 的学生有多少人。

输入格式

输入通过标准输入给出，格式如下：

$N$ $Q$ $C_1$ $\ldots$ $C_N$
$Query_1$
$\vdots$
$Query_Q$

输出格式

对于每个 2 x y 类型的查询，按顺序每行输出一个答案。

输入输出样例 #1

输入 #1

5 5
1 2 3 2 1
1 1 2
1 2 5
2 1 1
1 3 4
2 3 4

输出 #1

2
0

输入输出样例 #2

输入 #2

5 4
2 2 2 2 2
1 1 2
1 1 3
1 2 3
2 2 2

输出 #2

3

输入输出样例 #3

输入 #3

12 9
1 2 3 1 2 3 1 2 3 1 2 3
1 1 2
1 3 4
1 5 6
1 7 8
2 2 1
1 9 10
2 5 6
1 4 8
2 6 1

输出 #3

1
0
0

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq C_i, a, b, x, y \leq N$
• 对于 1 a b 查询，$a \neq b$
• 所有输入均为整数

样例解释 1

在第 $3$ 个查询时，学生 $1$ 已经与学生 $2,5$ 汇合。学生 $1,2,5$ 中属于班级 $1$ 的有 $2$ 人。在第 $5$ 个查询时，学生 $3$ 已经与学生 $4$ 汇合。学生 $3,4$ 中属于班级 $4$ 的有 $0$ 人。

样例解释 2

对于已经属于同一集体的学生，也可能会给出 1 a b 类型的查询。

由 ChatGPT 4.1 翻译