atcoder#ABC279F. [ABC279F] BOX

[ABC279F] BOX

题目描述

N N 個の箱 1,2,,N 1,2,\dots,N と、 10100 10^{100} 個のボール 1,2,,10100 1,2,\dots,10^{100} があります。 最初、箱 i i にはボール i i のみが入っています。

ここに以下の操作が合計 Q Q 回行われるので、処理してください。

操作にはタイプ 1,2,3 1,2,3 3 3 種類があります。

タイプ 1 1 : 箱 X X に箱 Y Y の中身を全て入れる。 この操作では X  Y X\ \neq\ Y が保証される。

1 X X Y Y

タイプ 2 2 : 現在いずれかの箱に入っているボールの数の合計を k k とすると、箱 X X にボール k+1 k+1 を入れる。

2 X X

タイプ 3 3 : ボール X X が入っている箱の番号を答える。

3 X X

输入格式

入力は以下の形式で標準入力から与えられる。
但し、 opi op_i i i 回目の操作を表す。

N N Q Q op1 op_1 op2 op_2 \vdots opQ op_Q

输出格式

各タイプ 3 3 の操作に対して、答えを 1 1 行に 1 1 つ、整数として出力せよ。

题目大意

NN 个箱子和无数个编号从 11 开始的球,第 ii 个箱子开始时只装了编号为 ii 的球。

QQ 次操作,每次操作分别可能为:

  • 1 X YYY 箱中的球全部放入 XX 箱。
  • 2 X 将目前最小的未被放到箱子里的球放到 XX 箱。
  • 3 X 查询 XX 球在哪个箱子中,输出该箱编号,输出间用换行隔开。
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
5
4
3
1
3

提示

制約

  • 入力は全て整数
  • 2  N  3 × 105 2\ \le\ N\ \le\ 3\ \times\ 10^5
  • 1  Q  3 × 105 1\ \le\ Q\ \le\ 3\ \times\ 10^5
  • タイプ 1 1 の操作について、 1  X,Y  N 1\ \le\ X,Y\ \le\ N かつ X  Y X\ \neq\ Y
  • タイプ 2 2 の操作について、 1  X  N 1\ \le\ X\ \le\ N
  • タイプ 3 3 の操作について、その時点でボール X X がいずれかの箱に入っている
  • タイプ 3 3 の操作が少なくとも 1 1 つ与えられる

Sample Explanation 1

この入力は 10 10 個の操作を含みます。 - 1 1 回目の操作はタイプ 3 3 です。ボール 5 5 は箱 5 5 に入っています。 - 2 2 回目の操作はタイプ 1 1 です。箱 1 1 に箱 4 4 の中身を全て入れます。 - 箱 1 1 の中身はボール 1,4 1,4 、箱 4 4 の中身は空になります。 - 3 3 回目の操作はタイプ 2 2 です。箱 1 1 にボール 6 6 を入れます。 - 4 4 回目の操作はタイプ 2 2 です。箱 4 4 にボール 7 7 を入れます。 - 5 5 回目の操作はタイプ 3 3 です。ボール 7 7 は箱 4 4 に入っています。 - 6 6 回目の操作はタイプ 1 1 です。箱 3 3 に箱 1 1 の中身を全て入れます。 - 箱 3 3 の中身はボール 1,3,4,6 1,3,4,6 、箱 1 1 の中身は空になります。 - 7 7 回目の操作はタイプ 3 3 です。ボール 4 4 は箱 3 3 に入っています。 - 8 8 回目の操作はタイプ 1 1 です。箱 1 1 に箱 4 4 の中身を全て入れます。 - 箱 1 1 の中身はボール 7 7 、箱 4 4 の中身は空になります。 - 9 9 回目の操作はタイプ 3 3 です。ボール 7 7 は箱 1 1 に入っています。 - 10 10 回目の操作はタイプ 3 3 です。ボール 6 6 は箱 3 3 に入っています。