Book Pile
题目描述
There is a pile of $N$ books on the table. Two types of operations are performed over this pile:
- a book is added to the top of the pile,
- top $K$ books are rotated. If there are less than $K$ books on the table, the whole pile is rotated.
First operation is denoted as $ADD(S)$ where $S$ is the name of the book, and the second operations is denoted as $ROTATE$.
The maximum number of books is no more than $40000$. All book names are non-empty sequences of no more than $3$ capital Latin letters. The names of the books can be non-unique.
题意概述
桌上有$N$本书叠成一堆。有两种操作:① 往书堆上加一本书;② 将最顶上的$K$本书翻转(若不足$K$本则全部翻转)。求操作$M$次后书本的顺序。
数据范围:$0 \le N \le 40000, \ 0 \le M \le 10^5, \ 0 \le K \le 40000$。
算法分析
这题可以用 Splay 来做,但其实有更简单的方法。
由于只会在顶上加书,也只会翻转顶上$K$本书,所以只要维护顶上$K$本书的状态即可。建一个长度为$K$的双端队列,每次翻转相当于向队列的另一端加书,队列长度大于$K$时在加书的另一端弹出一本书(这本书不会再受到翻转影响)。
Book Pile
https://regmsif.cf/2017/06/17/oi/book-pile/