← 返回题目列表

AtCoder · arc049_d

D. 交换海

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

問題文

在旅行时,高桥参观了一棵名为“交换空间”的神秘完美二叉树。

《换海》有高度 叶子的数量是 N+1 叶子的数量是 2^N 是一个完全二叉树。叶子是从左到右排列的。 该数字写为 1, 2, 3, ..., 2^N 。

另外,对于叶子以外的顶点,从上方 i 段目 (1 ≦ i ≦ N),从左起 j 番目 (1 ≦ j ≦ 2^{i-1}) 然后位置 将位置定义为 2^{i-1} + (j-1) 。

此外, 定义一个名为{\rm swap}(x) 的东西。这就是位置 操作是找到产生 x 的顶点并交换左右子树。

“交换海洋”如下 它可以处理 2 类型的查询。

类型 1: 给出了 k(1 ≦ k ≦ 2^N) ,所以从左边开始 找到写在第 k 片叶子上的数字。

类型 2: a, b(1 ≦ a ≦ b ≦ 2^N - 1) ,所以 转换为格式{\rm swap}(a), {\rm swap}(a+1), {\rm swap}(a+2), ..., {\rm swap}(b) 和此订单 使用运行。

高桥旅行回来后,他想制作自己的“交换空间”。然而,这很难,所以我决定为你做。

具体来说, 您将收到N 和Q 查询,因此请创建一个可以处理它们的“交换空间”。


入力

输入将以以下格式从标准输入给出。

N Q
t_1 a_1 b_1
t_2 a_2 b_2
:
t_Q a_Q b_Q
  • 1 行是一个整数 N(1 ≦ N ≦ 17), Q(1 ≦ Q ≦ 200,000) 用空格分隔。
  • 2 在 Q 行给出了查询的内容。这几天之一 i 行中,3 整数 t_i, a_i, b_i 用空格分隔。
  • t_i = 1 是类型 1 查询。 问题文本中的 a_i 代表 k ,b_i 必须是 0 。
  • t_i = 2 是类型 2 查询。 每个问句中都有 a_i, b_i 。 a, b 。

出力

每次出现类型1查询时,输出获得的值。每次输出时插入换行符。


入力例1

3 10
2 5 5
1 1 0
1 2 0
1 3 0
1 4 0
2 1 3
1 2 0
1 3 0
1 5 0
1 6 0

出力例1

1
2
4
3
8
5
4
3

在此示例中,类型 2 查询出现两次。

第一个类型 2 查询后,如下图所示。

D_img0

第二次类型 2 查询后,它将如下图所示。

D_img1