AT_abc279_f [ABC279F] BOX

题目描述

有 $N$ 个箱子 $1,2,\dots,N$，以及 $10^{100}$ 个球 $1,2,\dots,10^{100}$。最开始时，第 $i$ 个箱子中只放有第 $i$ 个球。

接下来会进行共计 $Q$ 次如下操作，请你依次处理：

操作分为三种类型，类型为 $1,2,3$。

类型 $1$：将箱子 $Y$ 中的所有球全部放入箱子 $X$。保证 $X \neq Y$。

1 $X$ $Y$

类型 $2$：设当前所有箱子中球的总数为 $k$，则将编号为 $k+1$ 的球放入箱子 $X$。

2 $X$

类型 $3$：询问编号为 $X$ 的球当前所在的箱子的编号。

3 $X$

输入格式

输入按以下格式从标准输入读入。
其中 $op_i$ 表示第 $i$ 次操作。

$N$ $Q$
$op_1$
$op_2$
$\vdots$
$op_Q$

输出格式

对于每个类型 $3$ 的操作，输出答案，每行一个整数。

输入输出样例 #1

输入 #1

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6

输出 #1

5
4
3
1
3

说明/提示

约束条件

• 输入均为整数。
• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• 对于类型 $1$ 的操作，$1 \leq X,Y \leq N$ 且 $X \neq Y$
• 对于类型 $2$ 的操作，$1 \leq X \leq N$
• 对于类型 $3$ 的操作，保证此时编号为 $X$ 的球一定在某个箱子中
• 至少有一次类型 $3$ 的操作

样例解释 1

本输入包含 $10$ 次操作。

• 第 $1$ 次操作为类型 $3$。球 $5$ 在箱子 $5$ 中。
• 第 $2$ 次操作为类型 $1$。将箱子 $4$ 的所有球放入箱子 $1$。
• 此时箱子 $1$ 中有球 $1,4$，箱子 $4$ 为空。
• 第 $3$ 次操作为类型 $2$。将球 $6$ 放入箱子 $1$。
• 第 $4$ 次操作为类型 $2$。将球 $7$ 放入箱子 $4$。
• 第 $5$ 次操作为类型 $3$。球 $7$ 在箱子 $4$ 中。
• 第 $6$ 次操作为类型 $1$。将箱子 $1$ 的所有球放入箱子 $3$。
• 此时箱子 $3$ 中有球 $1,3,4,6$，箱子 $1$ 为空。
• 第 $7$ 次操作为类型 $3$。球 $4$ 在箱子 $3$ 中。
• 第 $8$ 次操作为类型 $1$。将箱子 $4$ 的所有球放入箱子 $1$。
• 此时箱子 $1$ 中有球 $7$，箱子 $4$ 为空。
• 第 $9$ 次操作为类型 $3$。球 $7$ 在箱子 $1$ 中。
• 第 $10$ 次操作为类型 $3$。球 $6$ 在箱子 $3$ 中。

由 ChatGPT 4.1 翻译