← 返回题目列表

Codeforces · 1620/E

E. 替换数字

中文机器翻译题面 查看原题

您有一个整数数组(最初为空)。

您必须执行 $$$q$$$ 查询。每个查询属于以下两种类型之一:

- "$$$1$$$ $$$x$$$" — 将元素 $$$x$$$ 添加到数组末尾;
- "$$$2$$$ $$$x$$$ $$$y$$$" — 将数组中所有出现的 $$$x$$$ 替换为 $$$y$$$。

执行所有查询后查找结果数组。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行包含查询(每行一个)。每个查询属于以下两种类型之一:

- "$$$1$$$ $$$x$$$" ($$$1 \le x \le 5 \cdot 10^5$$$);
- “$$$2$$$ $$$x$$$ $$$y$$$” ($$$1 \le x, y \le 5 \cdot 10^5$$$)。

保证至少有一个第一类型的查询。

输出

在一行中,打印 $$$k$$$ 整数 - 执行所有查询后的结果数组,其中 $$$k$$$ 是第一种类型的查询数量。

示例

输入 #1

7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3

输出 #1

3 2 2 3 2

输入 #2

4
1 1
1 2
1 1
2 2 2

输出 #2

1 2 1

输入 #3

8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7

输出 #3

1 3 3 7

注意

在第一个示例中,数组更改如下:

$$$[]$$$ $$$\rightarrow$$$ $$$[3]$$$ $$$\rightarrow$$$ $$$[3, 1]$$$ $$$\rightarrow$$$ $$$[3, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 1, 2]$$$ $$$\rightarrow$$$ $$$[3, 2, 2, 3, 2]$$$。

在第二个示例中,数组更改如下:

$$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 2]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$ $$$\rightarrow$$$ $$$[1, 2, 1]$$$。

在第三个示例中,数组更改如下:

$$$[]$$$ $$$\rightarrow$$$ $$$[]$$$ $$$\rightarrow$$$ $$$[1]$$$ $$$\rightarrow$$$ $$$[1, 4]$$$ $$$\rightarrow$$$ $$$[1, 4, 2]$$$ $$$\rightarrow$$$ $$$[1, 4, 4]$$$ $$$\rightarrow$$$ $$$[1, 3, 3]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 2]$$$ $$$\rightarrow$$$ $$$[1, 3, 3, 7]$$$。