309069: CF1619H. Permutation and Queries
Memory Limit:256 MB
Time Limit:4 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Permutation and Queries
题意翻译
## 题目描述 给定由 $1 \sim n$ 构成的排列 $p$,有两种操作: - `1 x y`:交换 $p_{x}$ 和 $p_{y}$。 - `2 i k`:给出 $i$ 的初始值,令 $i \gets p_{i}$ 执行 $k$ 次,最后输出 $i$。 至少有一个第二类操作。 **【输入格式】** 第一行包含两个整数 $n, q$($1 \le n,q \le 10^{5}$),分别表示数的个数和操作次数。 第二行包含 $n$ 个整数 $q_{1}, q_{2}, \ldots, q_{n}$。 接下来的 $q$ 行每行包含三个整数,表示一种操作。 **【输出格式】** 每行一个整数,表示每一个第二类查询的结果。题目描述
You are given a permutation $ p $ of $ n $ elements. A permutation of $ n $ elements is an array of length $ n $ containing each integer from $ 1 $ to $ n $ exactly once. For example, $ [1, 2, 3] $ and $ [4, 3, 5, 1, 2] $ are permutations, but $ [1, 2, 4] $ and $ [4, 3, 2, 1, 2] $ are not permutations. You should perform $ q $ queries. There are two types of queries: - $ 1 $ $ x $ $ y $ — swap $ p_x $ and $ p_y $ . - $ 2 $ $ i $ $ k $ — print the number that $ i $ will become if we assign $ i = p_i $ $ k $ times.输入输出格式
输入格式
The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 10^5 $ ). The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ . Each of the next $ q $ lines contains three integers. The first integer is $ t $ ( $ 1 \le t \le 2 $ ) — type of query. If $ t = 1 $ , then the next two integers are $ x $ and $ y $ ( $ 1 \le x, y \le n $ ; $ x \ne y $ ) — first-type query. If $ t = 2 $ , then the next two integers are $ i $ and $ k $ ( $ 1 \le i, k \le n $ ) — second-type query. It is guaranteed that there is at least one second-type query.
输出格式
For every second-type query, print one integer in a new line — answer to this query.
输入输出样例
输入样例 #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