P2596 [ZJOI2006] Bookshelf

Xiao T has a very large bookcase. Its structure is a bit special: the books in the bookcase are stacked in a single column from top to bottom. She labels each book with the positive integers from $1$ to $n$. When Xiao T reads, each time she takes out one book, and after finishing it, she puts it back into the bookcase and then takes the next one. Because the books are so attractive, she often forgets the exact position where the book was originally placed. However, Xiao T has a very good memory, so when she puts a book back, she can at least place it near where it was taken from. For example, if when she took the book there were $x$ books above it, then when putting it back, there can only be $x - 1$, $x$, or $x + 1$ books above it. Of course, there are special cases, such as when the phone rings or a friend visits while she is reading. At these times, the careless Xiao T may casually put the book at the very top or the very bottom of all the books in the bookcase, and then walk away. Over time, the order of the books in Xiao T’s bookcase becomes more and more chaotic, making it increasingly difficult to find a specific labeled book. So she asks you to write a library management program to process her operations while reading and answer two types of queries: - What is the position of the book with ID $x$ in the bookcase. - What is the ID of the $i$-th book from top to bottom.

The first line contains two integers, representing the number of books $n$ and the number of commands $m$. The second line contains $n$ integers. The $i$-th integer $p_i$ is the ID of the $i$-th book from the top at the beginning. Then there are $m$ lines, each describing an operation. Each line starts with a string $op$. - If $op$ is `Top`, followed by an integer $s$, move the book with ID $s$ to the very top. - If $op$ is `Bottom`, followed by an integer $s$, move the book with ID $s$ to the very bottom. - If $op$ is `Insert`, followed by two integers $s, t$, then if there are $x$ books above the book with ID $s$, when putting it back there should be $x + t$ books above it. - If $op$ is `Ask`, followed by an integer $s$, ask how many books are above the book with ID $s$. - If $op$ is `Query`, followed by an integer $s$, ask for the ID of the $s$-th book from the top.

For each query, output a single integer on its own line as the answer.

Constraints For $100\%$ of the testdata, it is guaranteed that: - $3 \leq n, m \leq 8 \times 10^4$. - $p_i$ is a permutation of $1$ to $n$. - $1 \leq s \leq n$, $-1 \leq t \leq 1$, and $op$ is one of the five strings above. - When there is no book above the book with ID $s$, the operation `Insert s -1` will not be performed. - When there is no book below the book with ID $s$, the operation `Insert s 1` will not be performed. Translated by ChatGPT 5