P2596 [ZJOI2006] 书架
题目描述
小 T 有一个很大的书柜,书柜里的书从上到下堆成一列。她用 1∼n 的正整数给每本书都编了号。
小 T 看书时,每次取出一本书,看完后放回书柜,再取下一本。由于这些书太有吸引力了,她看完后常常忘记原来放在书柜的什么位置。不过小 T 的记忆力非常好,所以每次放书时至少能把书放在取出时的位置附近:若取出某本书时这本书上面有 x 本书,那么放回时这本书上面只可能有 x−1、x 或 x+1 本书。
当然也有特殊情况:看书时突然电话响了或者有朋友来访,这时粗心的小 T 会随手把书放在所有书的最上面或者最下面,然后转身离开。
久而久之,书柜里的书的顺序越来越乱,找到特定编号的书变得越来越困难。于是她请你编写一个图书管理程序,处理她看书时的操作,并回答以下两种提问:
∙编号为 s 的书上面有几本书;
∙从上往下数第 s 本书的编号是多少。
具体来说,程序需要支持以下五种命令:
1.命令 Top s:把编号为 s 的书放到所有书的最上面;
2.命令 Bottom s:把编号为 s 的书放到所有书的最下面;
3.命令 Insert s t:设编号为 s 的书上面现在有 x 本书,则在放回这本书后,它的上面有 x+t 本书。由于 t 只能是 −1 或 1,这等价于让这本书与它上面或下面相邻的一本书交换位置;
4.命令 Ask s:输出编号为 s 的书上面有几本书;
5.命令 Query s:输出从上往下数第 s 本书的编号。
输入格式
第一行输入两个整数 n,m(3≦n,m≦8×104) 代表书的数量以及命令条数。
第二行输入 n 个整数 $p_1, p_2, \dots, p_n \left(1 \leqq p_i \leqq n\right)$,其中 pi 代表初始时从上往下数第 i 本书的编号。保证 p1,p2,…,pn 是 1∼n 的一个排列。
此后 m 行,第 i 行输入一条命令,格式为以下四种之一:
∙Top s 或 Bottom s(1≦s≦n),其中 s 代表被移动的书的编号;
$\hspace{23pt}\bullet\,\texttt{Insert } s\ t \left(1 \leqq s \leqq n;\ -1 \leqq t \leqq 1\right)$,其中 s 代表书的编号,t 代表这本书上面的书的变化量;
$\hspace{23pt}\bullet\,\texttt{Ask } s \left(1 \leqq s \leqq n\right)$,其中 s 代表被询问的书的编号;
$\hspace{23pt}\bullet\,\texttt{Query } s \left(1 \leqq s \leqq n\right)$,其中 s 代表从上往下数的名次。
保证当编号为 s 的书上面没有书时,不会出现命令 Insert s −1;当编号为 s 的书下面没有书时,不会出现命令 Insert s 1。也就是说,任意时刻书柜中书的顺序都是 1∼n 的一个排列。
输出格式
对于每条 Ask 或 Query 命令,新起一行输出一个整数:Ask 输出这本书上面的书的数量,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 解释
初始时从上往下书的编号依次为 {1,3,2,7,5,8,10,4,9,6}。各条命令执行后如下:
∙命令 Query 3:第 3 本书的编号为 2;
∙命令 Top 5:顺序变为 {5,1,3,2,7,8,10,4,9,6};
∙命令 Ask 6:编号为 6 的书上面有 9 本书;
∙命令 Bottom 3:顺序变为 {5,1,2,7,8,10,4,9,6,3};
∙命令 Ask 3:编号为 3 的书上面有 9 本书;
∙命令 Top 6:顺序变为 {6,5,1,2,7,8,10,4,9,3};
∙命令 Insert 4 −1:编号为 4 的书与它上面的 10 交换,顺序变为 {6,5,1,2,7,8,4,10,9,3};
∙命令 Query 5:第 5 本书的编号为 7;
∙命令 Query 2:第 2 本书的编号为 5;
∙命令 Ask 2:编号为 2 的书上面有 3 本书。
因此依次输出 2,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 解释
初始时从上往下书的编号依次为 {5,2,4,1,3}。各条命令执行后如下:
∙命令 Ask 2:编号为 2 的书上面有 1 本书;
∙命令 Query 4:第 4 本书的编号为 1;
∙命令 Insert 3 −1:编号为 3 的书与它上面的 1 交换,顺序变为 {5,2,4,3,1};
∙命令 Ask 3:编号为 3 的书上面有 3 本书;
∙命令 Top 3:顺序变为 {3,5,2,4,1};
∙命令 Query 2:第 2 本书的编号为 5。
因此依次输出 1,1,3,5。
提示
对于 100% 的数据,3≦n,m≦8×104,pi 是 1∼n 的排列,1≦s≦n,−1≦t≦1,且命令只可能是上述五种字符串之一。