LG#P2596. [ZJOI2006] 书架

[ZJOI2006] 书架

P2596 [ZJOI2006] 书架

题目描述

\hspace{15pt}小 T 有一个很大的书柜,书柜里的书从上到下堆成一列。她用 1∼n1 \sim n 的正整数给每本书都编了号。

\hspace{15pt}小 T 看书时,每次取出一本书,看完后放回书柜,再取下一本。由于这些书太有吸引力了,她看完后常常忘记原来放在书柜的什么位置。不过小 T 的记忆力非常好,所以每次放书时至少能把书放在取出时的位置附近:若取出某本书时这本书上面有 xx 本书,那么放回时这本书上面只可能有 x−1x-1、xx 或 x+1x+1 本书。

\hspace{15pt}当然也有特殊情况:看书时突然电话响了或者有朋友来访,这时粗心的小 T 会随手把书放在所有书的最上面或者最下面,然后转身离开。

\hspace{15pt}久而久之,书柜里的书的顺序越来越乱,找到特定编号的书变得越来越困难。于是她请你编写一个图书管理程序,处理她看书时的操作,并回答以下两种提问:

∙ \hspace{23pt}\bullet\,编号为 ss 的书上面有几本书;

∙ \hspace{23pt}\bullet\,从上往下数第 ss 本书的编号是多少。

\hspace{15pt}具体来说,程序需要支持以下五种命令:

1. {\hspace{20pt}}_\texttt{1.}\,命令 Top s\texttt{Top } s:把编号为 ss 的书放到所有书的最上面;

2. {\hspace{20pt}}_\texttt{2.}\,命令 Bottom s\texttt{Bottom } s:把编号为 ss 的书放到所有书的最下面;

3. {\hspace{20pt}}_\texttt{3.}\,命令 Insert s t\texttt{Insert } s\ t:设编号为 ss 的书上面现在有 xx 本书,则在放回这本书后,它的上面有 x+tx+t 本书。由于 tt 只能是 −1-1 或 11,这等价于让这本书与它上面或下面相邻的一本书交换位置;

4. {\hspace{20pt}}_\texttt{4.}\,命令 Ask s\texttt{Ask } s:输出编号为 ss 的书上面有几本书;

5. {\hspace{20pt}}_\texttt{5.}\,命令 Query s\texttt{Query } s:输出从上往下数第 ss 本书的编号。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(3≦n,m≦8×104)n, m \left(3 \leqq n, m \leqq 8 \times 10^4\right) 代表书的数量以及命令条数。

\hspace{15pt}第二行输入 nn 个整数 $p_1, p_2, \dots, p_n \left(1 \leqq p_i \leqq n\right)$,其中 pip_i 代表初始时从上往下数第 ii 本书的编号。保证 p1,p2,…,pnp_1, p_2, \dots, p_n 是 1∼n1 \sim n 的一个排列。

\hspace{15pt}此后 mm 行,第 ii 行输入一条命令,格式为以下四种之一:

∙ Top s\hspace{23pt}\bullet\,\texttt{Top } s 或 Bottom s(1≦s≦n)\texttt{Bottom } s \left(1 \leqq s \leqq n\right),其中 ss 代表被移动的书的编号;

$\hspace{23pt}\bullet\,\texttt{Insert } s\ t \left(1 \leqq s \leqq n;\ -1 \leqq t \leqq 1\right)$,其中 ss 代表书的编号,tt 代表这本书上面的书的变化量;

$\hspace{23pt}\bullet\,\texttt{Ask } s \left(1 \leqq s \leqq n\right)$,其中 ss 代表被询问的书的编号;

$\hspace{23pt}\bullet\,\texttt{Query } s \left(1 \leqq s \leqq n\right)$,其中 ss 代表从上往下数的名次。

\hspace{15pt}保证当编号为 ss 的书上面没有书时,不会出现命令 Insert s −1\texttt{Insert } s\ -1;当编号为 ss 的书下面没有书时,不会出现命令 Insert s 1\texttt{Insert } s\ 1。也就是说,任意时刻书柜中书的顺序都是 1∼n1 \sim n 的一个排列。

输出格式

\hspace{15pt}对于每条 Ask\texttt{Ask} 或 Query\texttt{Query} 命令,新起一行输出一个整数:Ask\texttt{Ask} 输出这本书上面的书的数量,Query\texttt{Query} 输出对应位置上的书的编号。所有答案按命令的先后顺序输出。

测试样例

10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2
2
9
9
7
5
3

样例 1 解释

\hspace{15pt}初始时从上往下书的编号依次为 {1,3,2,7,5,8,10,4,9,6}\{1, 3, 2, 7, 5, 8, 10, 4, 9, 6\}。各条命令执行后如下:

∙ \hspace{23pt}\bullet\,命令 Query 3\texttt{Query } 3:第 33 本书的编号为 22;

∙ \hspace{23pt}\bullet\,命令 Top 5\texttt{Top } 5:顺序变为 {5,1,3,2,7,8,10,4,9,6}\{5, 1, 3, 2, 7, 8, 10, 4, 9, 6\};

∙ \hspace{23pt}\bullet\,命令 Ask 6\texttt{Ask } 6:编号为 66 的书上面有 99 本书;

∙ \hspace{23pt}\bullet\,命令 Bottom 3\texttt{Bottom } 3:顺序变为 {5,1,2,7,8,10,4,9,6,3}\{5, 1, 2, 7, 8, 10, 4, 9, 6, 3\};

∙ \hspace{23pt}\bullet\,命令 Ask 3\texttt{Ask } 3:编号为 33 的书上面有 99 本书;

∙ \hspace{23pt}\bullet\,命令 Top 6\texttt{Top } 6:顺序变为 {6,5,1,2,7,8,10,4,9,3}\{6, 5, 1, 2, 7, 8, 10, 4, 9, 3\};

∙ \hspace{23pt}\bullet\,命令 Insert 4 −1\texttt{Insert } 4\ -1:编号为 44 的书与它上面的 1010 交换,顺序变为 {6,5,1,2,7,8,4,10,9,3}\{6, 5, 1, 2, 7, 8, 4, 10, 9, 3\};

∙ \hspace{23pt}\bullet\,命令 Query 5\texttt{Query } 5:第 55 本书的编号为 77;

∙ \hspace{23pt}\bullet\,命令 Query 2\texttt{Query } 2:第 22 本书的编号为 55;

∙ \hspace{23pt}\bullet\,命令 Ask 2\texttt{Ask } 2:编号为 22 的书上面有 33 本书。

\hspace{15pt}因此依次输出 2,9,9,7,5,32, 9, 9, 7, 5, 3。

5 6
5 2 4 1 3
Ask 2
Query 4
Insert 3 -1
Ask 3
Top 3
Query 2
1
1
3
5

样例 2 解释

\hspace{15pt}初始时从上往下书的编号依次为 {5,2,4,1,3}\{5, 2, 4, 1, 3\}。各条命令执行后如下:

∙ \hspace{23pt}\bullet\,命令 Ask 2\texttt{Ask } 2:编号为 22 的书上面有 11 本书;

∙ \hspace{23pt}\bullet\,命令 Query 4\texttt{Query } 4:第 44 本书的编号为 11;

∙ \hspace{23pt}\bullet\,命令 Insert 3 −1\texttt{Insert } 3\ -1:编号为 33 的书与它上面的 11 交换,顺序变为 {5,2,4,3,1}\{5, 2, 4, 3, 1\};

∙ \hspace{23pt}\bullet\,命令 Ask 3\texttt{Ask } 3:编号为 33 的书上面有 33 本书;

∙ \hspace{23pt}\bullet\,命令 Top 3\texttt{Top } 3:顺序变为 {3,5,2,4,1}\{3, 5, 2, 4, 1\};

∙ \hspace{23pt}\bullet\,命令 Query 2\texttt{Query } 2:第 22 本书的编号为 55。

\hspace{15pt}因此依次输出 1,1,3,51, 1, 3, 5。

提示

\hspace{15pt}对于 100%100\% 的数据,3≦n,m≦8×1043 \leqq n, m \leqq 8 \times 10^4,pip_i 是 1∼n1 \sim n 的排列,1≦s≦n1 \leqq s \leqq n,−1≦t≦1-1 \leqq t \leqq 1,且命令只可能是上述五种字符串之一。