UOJ Logo

NOI.AC

#33. bst

统计

二叉交换树

题目描述

小 $D$ 最近对二叉树以及交换非常感兴趣,他想要把这两个东西合在一起,于是他得到了二叉交换树Binary Swap Tree,简称 BST)。

二叉交换树是一棵高度为 $n+1$ 的满二叉树(即满足前 $n$ 层节点均有且仅由两个孩子,而第 $n+1$ 层节点都是叶节点的二叉树)。

一棵二叉交换树共有 $2^n$ 个叶子,从左到右依次写着 $L_1,L_2,L_3,\cdots,L_{2^n}$。它还有 $2^n-1$ 个非叶节点,我们用 $(i,j)$ 表示此时从上到下第 $i$ 层的第 $j$ 个节点,我们还可以用 $T_{2^{i-1}+j-1}$ 表示这个节点。

作为一棵二叉交换树,自然要支持交换操作。我们定义 $swap(u)$ 表示交换节点 $T_u$ 的左右子树(即原来的左子树变为右子树,而原来的右子树变为左子树)。

注意:在交换操作之后:

  • 原来的 $T_x$ 和现在的 $T_x$ 可能并不是一个节点,这是因为 $(i,j)$ 表示的是当前树上处于这个位置的节点;
  • 但是,$L_x$ 始终表示同一个叶子,这是因为 $L_x$ 是写在叶子上的,会和节点位置的变化而一同变化

小 $D$ 现在进行了 $q$ 次操作,操作有两种:

  • 1 L R 表示依次进行 $swap(L),swap(L+1),swap(L+2),\cdots,swap(R)$ 的操作(注意在相邻两次操作之间,节点的重编号也会被进行)。
  • 2 x 表示询问当前从左到右第 $x$ 个叶子上面写着什么。

然而小 $D$ 无法维护过于巨大的树,请你帮帮他。

输入格式

第一行两个空格隔开的整数 $n,q$,意义如题面所示。

接下来 $q$ 行,每行两个或三个整数,表示一次询问。其格式如题面所示。

输出格式

对于每一个操作 2,输出一行一个整数表示答案。如果这个叶子写着 $L_a$,则你只要输出 $a$ 即可。

样例输入 1

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

样例输出 1

1
2
4
3
8
5
4
3

样例解释 1

初始时,树的形态如图所示:

(见下发文件 pic1.png

第一次交换操作是 $swap(5)$,即对上图中的红色节点进行了操作,得到:

(见下发文件 pic2.png

接下来第二次交换操作先进行了 $swap(1)$,即上图中的红色节点,得到:

(见下发文件 pic3.png

然后进行了 $swap(2)$,即上图中的红色节点,得到:

(见下发文件 pic4.png

最后进行了 $swap(3)$,即上图中的红色节点,得到:

(见下发文件 pic5.png

样例输入输出 2 & 3 & 4 & 5

见下发文件 ex_bst2.in/outex_bst3.in/outex_bst4.in/out 以及 ex_bst5.in/out。其中 ex_bst3.in 满足特殊性质一,而 ex_bst4.in 满足特殊性质二(见 “数据规模与约定” 一节)。

数据规模与约定

本题共 $20$ 个测试数据,每个测试数据 $5$ 分。

对于前 $10\%$ 的数据,$1\le n\le 3$,$1\le q\le 10$;
对于另 $20\%$ 的数据,$1\le n\le 10$,$1\le q\le 2000$;
对于另 $\ \ 5\%$ 的数据,$1\le n\le 17$,$1\le q\le 2\times 10^5$,且满足特殊性质一;
对于另 $10\%$ 的数据,$1\le n\le 17$,$1\le q\le 2\times 10^5$,且满足特殊性质二;
对于另 $25\%$ 的数据,$1\le n\le 17$,$1\le q\le 2\times 10^5$;
对于另 $\ \ 5\%$ 的数据,满足特殊性质一;
对于另 $10\%$ 的数据,满足特殊性质二;
对于 $100\%$ 的数据,有 $1\le n\le 20$,$1\le q\le 10^6$,$1\le L\le R\lt 2^n$,$1\le x\le 2^n$。

其中,特殊性质一表示:对于操作 1,存在整数 $k$ $(0\le k\lt n)$,使得 $L=2^k$ 且 $R=2^{k+1}-1$。而特殊性质二表示:对于操作 1,存在整数 $x,y$ $(0\le x\lt y\le n)$,使得 $L=2^x$ 且 $R=2^y-1$。

友情提醒:本题输入输出数据量可能很大,对于使用 C++ 语言的选手,如果使用 (std::)cin/cout 进行输入输出将会直接导致 $q$ 较大的部分测试点超时,请关闭流同步或改为使用 scanf/printf 才有可能得到这一部分的分数。

时间限制:$2\mathtt{s}$

空间限制:$512\mathtt{MB}$

样例输入输出

样例数据