Replace the Numbers
题意翻译
维护一个数列,这个数列初始为空。
对于这个数列,总共有 $q$ 次操作,每次操作分为如下两个种类:
1. `1 x`,意为在数列末尾加一个数字
2. `2 x y`,意为将数列中所有值为 $x$ 的数的值替换成 $y$
请在 $q$ 次操作后,输出这个数列。
$1\leqslant q,x,y\leqslant5*10^5$
题目描述
You have an array of integers (initially empty).
You have to perform $ q $ queries. Each query is of one of two types:
- " $ 1 $ $ x $ " — add the element $ x $ to the end of the array;
- " $ 2 $ $ x $ $ y $ " — replace all occurrences of $ x $ in the array with $ y $ .
Find the resulting array after performing all the queries.
输入输出格式
输入格式
The first line contains a single integer $ q $ ( $ 1 \le q \le 5 \cdot 10^5 $ ) — the number of queries.
Next $ q $ lines contain queries (one per line). Each query is of one of two types:
- " $ 1 $ $ x $ " ( $ 1 \le x \le 5 \cdot 10^5 $ );
- " $ 2 $ $ x $ $ y $ " ( $ 1 \le x, y \le 5 \cdot 10^5 $ ).
It's guaranteed that there is at least one query of the first type.
输出格式
In a single line, print $ k $ integers — the resulting array after performing all the queries, where $ k $ is the number of queries of the first type.
输入输出样例
输入样例 #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
说明
In the first example, the array changes as follows:
$ [] $ $ \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] $ .
In the second example, the array changes as follows:
$ [] $ $ \rightarrow $ $ [1] $ $ \rightarrow $ $ [1, 2] $ $ \rightarrow $ $ [1, 2, 1] $ $ \rightarrow $ $ [1, 2, 1] $ .
In the third example, the array changes as follows:
$ [] $ $ \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] $ .