← 返回题目列表

Codeforces · 1619/H

H. 排列和查询

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

给你一个 $$$n$$$ 元素的排列 $$$p$$$。 $$$n$$$ 元素的排列是一个长度为 $$$n$$$ 的数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次。例如,$$$[1, 2, 3]$$$ 和 $$$[4, 3, 5, 1, 2]$$$ 是排列,但 $$$[1, 2, 4]$$$ 和 $$$[4, 3, 2, 1, 2]$$$ 不是排列。您应该执行 $$$q$$$ 查询。

有两种类型的查询:

- $$$1$$$ $$$x$$$ $$$y$$$ — 交换 $$$p_x$$$ 和 $$$p_y$$$。
- $$$2$$$ $$$i$$$ $$$k$$$ — 如果我们分配 $$$i = p_i$$$ $$$k$$$ 次,则打印 $$$i$$$ 将变成的数字。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$。

接下来的 $$$q$$$ 行包含三个整数。第一个整数是 $$$t$$$ ($$$1 \le t \le 2$$$) — 查询类型。如果 $$$t = 1$$$,则接下来的两个整数是 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \ne y$$$) — 第一类查询。如果 $$$t = 2$$$,则接下来的两个整数是 $$$i$$$ 和 $$$k$$$ ($$$1 \le i, k \le n$$$) — 第二种类型查询。

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

输出

对于每个第二类查询,在新行中打印一个整数 - 回答此查询。

示例

输入 #1

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

输出 #1

4
1
2

输入 #2

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

输出 #2

3
5
4
2
3
3
3
1

注意

在第一个示例中 $$$p = \{5, 3, 4, 2, 1\}$$$。

第一个查询是打印 $$$p_3$$$。答案是$$$4$$$。

第二个查询是打印 $$$p_{p_1}$$$。答案是$$$1$$$。

第三个查询是交换$$$p_1$$$ 和$$$p_3$$$。现在$$$p = \{4, 3, 5, 2, 1\}$$$。

第四个查询是打印 $$$p_{p_1}$$$。答案是$$$2$$$。