← 返回题目列表

AtCoder · typical90_ar

044. 移位和交换(★3)

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

配点: 3 点

問題文

长度 小于或等于 N 整数序列 给出 \{A_n\} 。下面 请回答 Q 查询。

  • T_i=1 :序列号 x 項 (=A_x)和值 交换 y 項 (=A_y的值)。
  • T_i=2 :将序列向右移动。也就是说, 查找\{A_n\} = A_N, A_1, A_2, \cdots, A_{N-1} 。
  • T_i=3 :序列号 x 項 (=A_x的值)。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_n \leq 10^9 (1 \leq n \leq N)
  • 1 \leq T_i \leq 3 (1 \leq i \leq Q)
  • T_i = 1 如果 1 \leq x_i, y_i \leq N 和 x_i \neq y_i
  • T_i = 2 如果 x_i=y_i=0
  • T_i = 3 如果 1 \leq x_i \leq N 和 y_i=0
  • 所有输入值均为整数 按给定顺序输出查询

入力

输入是按以下格式从标准输入给出的。

N Q
A_1 A_2 \cdots A_N
T_1 x_1 y_1
\vdots
T_Q x_Q y_Q

出力

T_i=3 的答案,并以换行符分隔。


入力例 1

8 5
6 17 2 4 17 19 1 7
2 0 0
1 7 2
1 2 6
1 4 5
3 4 0

出力例 1

4

最初,序列是 6, 17, 2, 4, 17, 19, 1, 7 。
第一个查询将数字序列向右移动。经过此操作后,数列变为 7, 6, 17, 2, 4, 17, 19, 1 。 对于
在第二个查询中,数字 7 节与节 2 交换条款。经过此操作后,数列变为 7, 19, 17, 2, 4, 17, 6, 1 。 对于
在第三个查询中,数字 2 节与节 6 交换条款。经过此操作后,数列变为 7, 17, 17, 2, 4, 19, 6, 1 。 对于
在第四个查询中,数字 4 节与节 5 交换条款。经过此操作后,数列变为 7, 17, 17, 4, 2, 19, 6, 1 。 对于
在第五个查询中,数字 4 术语值 A_4=4 。


入力例 2

9 6
16 7 10 2 9 18 15 20 5
2 0 0
1 1 4
2 0 0
1 8 5
2 0 0
3 6 0

出力例 2

18

最初,序列是 16, 7, 10, 2, 9, 18, 15, 20, 5 。
第一次查询后,编号顺序为 5, 16, 7, 10, 2, 9, 18, 15, 20 。 对于
第二次查询后,编号顺序为 10, 16, 7, 5, 2, 9, 18, 15, 20 。 对于
第三次查询后,编号顺序为 20, 10, 16, 7, 5, 2, 9, 18, 15 。 对于
第四次查询后,编号顺序为 20, 10, 16, 7, 18, 2, 9, 5, 15 。 对于
第五次查询后,序列为 15, 20, 10, 16, 7, 18, 2, 9, 5 。 对于
在第六个查询中,数量 6 术语值 A_6=18 。


入力例 3

11 18
23 92 85 34 21 63 12 9 81 44 96
3 10 0
3 5 0
1 3 4
2 0 0
1 4 11
3 11 0
1 3 5
2 0 0
2 0 0
3 9 0
2 0 0
3 6 0
3 10 0
1 6 11
2 0 0
3 10 0
3 4 0
3 5 0

出力例 3

44
21
34
63
85
63
21
34
96