102734: [AtCoder]ABC273 E - Notebook
Description
Score : $500$ points
Problem Statement
We have an integer sequence $A$ and a notebook. The notebook has $10^9$ pages.
You are given $Q$ queries. Each query is of one of the following four kinds:
ADD $x$: append an integer $x$ to the tail of $A$.
DELETE: remove the last term of $A$ if $A$ is not empty; do nothing otherwise.
SAVE $y$: erase the sequence recorded on the $y$-th page of the notebook, and record the current $A$ onto the $y$-th page.
LOAD $z$: replace $A$ with the sequence recorded on the $z$-th page of the notebook.
Initially, $A$ is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process $Q$ queries successively in the given order and print the last term of $A$ after processing each query.
The use of fast input and output methods is recommended because of potentially large input and output.
Constraints
- $1 \leq Q \leq 5 \times 10^5$
- $1 \leq x, y, z \leq 10^9$
- $Q$, $x$, $y$, and $z$ are integers.
- Each of the given queries is of one of the four kinds in the Problem Statement.
Input
The input is given from Standard Input in the following format:
$Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$
Output
For each $i = 1, 2, \ldots, Q$, let $X_i$ be the last element of $A$ after processing up to the $i$-th query, or let $X_i := -1$ if $A$ is empty, and print them in the following format:
$X_1$ $X_2$ $\ldots$ $X_Q$
Sample Input 1
11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1
Sample Output 1
3 3 4 4 3 -1 -1 4 4 -1 4
Initially, $A$ is an empty sequence, so $A = ()$, and an empty sequence is recorded on each page of the notebook.
- By the $1$-st query, $3$ is appended to the tail of $A$, resulting in $A = (3)$.
- By the $2$-nd query, the sequence recorded on the $1$-st page of the notebook becomes $(3)$. It remains that $A = (3)$.
- By the $3$-rd query, $4$ is appended to the tail of $A$, resulting in $A = (3, 4)$.
- By the $4$-th query, the sequence recorded on the $2$-nd page of the notebook becomes $(3, 4)$. It remains that $A = (3, 4)$.
- By the $5$-th query, $A$ is replaced by $(3)$, which is recorded on the $1$-st page of the notebook, resulting in $A = (3)$.
- By the $6$-th query, the last term of $A$ is removed, resulting in $A = ()$.
- By the $7$-th query, nothing happens because $A$ is already empty. It remains that $A = ()$.
- By the $8$-th query, $A$ is replaced by $(3,4)$, which is recorded on the $2$-nd page of the notebook, resulting in $A = (3, 4)$.
- By the $9$-th query, the sequence recorded on the $1$-st page of the notebook becomes $(3, 4)$. It remains that $A = (3, 4)$.
- By the $10$-th query, $A$ is replaced by $()$, which is recorded on the $3$-rd page of the notebook, resulting in $A = ()$.
- By the $11$-th query, $A$ is replaced by $(3, 4)$, which is recorded on the $1$-st page of the notebook, resulting in $A = (3, 4)$.
Sample Input 2
21 ADD 4 ADD 3 DELETE ADD 10 LOAD 7 SAVE 5 SAVE 5 ADD 4 ADD 4 ADD 5 SAVE 5 ADD 2 DELETE ADD 1 SAVE 5 ADD 7 ADD 8 DELETE ADD 4 DELETE LOAD 5
Sample Output 2
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1
Input
题意翻译
有一个版本保存系统,共有 $10^9$ 个版本,每个版本初始都为空列表,还需要维护一个列表(后称为“当前列表”)。 您需要实现如下四种操作: - `ADD x`:在当前列表的末尾添加 $x$ - `DELETE`:如果当前列表非空,把当前列表的末尾最后一个数删除。否则,什么也不做。 - `SAVE x`:把当前列表保存至第 $x$ 版本(在此后完成的操作不会在第 $x$ 版本中出现,而且保存后当前列表不清空) - `LOAD x`:把当前列表变成第 $x$ 版本(直接赋值,而不是添加,而且保存后第 $x$ 版本不清空) 给定 $q$ 次操作,每次操作是以上四种操作,求每次操作**后**的当前列表的末尾最后一个数(若数组为空输出 $-1$)。Output
分数:$500$分
问题描述
我们有一个整数序列$A$和一本笔记本。笔记本有$10^9$页。
你会得到$Q$个查询。每个查询属于以下四种之一:
ADD $x$: 将整数$x$添加到$A$的末尾。
DELETE: 如果$A$不为空,则删除$A$的最后一个项;否则什么也不做。
SAVE $y$: 删除笔记本上第$y$页记录的序列,并将当前的$A$记录到第$y$页。
LOAD $z$: 将笔记本上第$z$页记录的序列替换为$A$。
最初,$A$是一个空序列,笔记本的每一页上都记录了一个空序列。按照给定的顺序依次处理$Q$个查询,并在处理每个查询后打印出$A$的最后一个元素。
由于可能有大量输入和输出,建议使用快速输入和输出方法。
约束条件
- $1 \leq Q \leq 5 \times 10^5$
- $1 \leq x, y, z \leq 10^9$
- $Q$,$x$,$y$和$z$都是整数。
- 给定的每个查询都属于问题描述中四种类型的其中之一。
输入
输入从标准输入中给出,格式如下:
$Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$
输出
对于每个$i = 1, 2, \ldots, Q$,如果在处理完前$i$个查询后$A$不为空,则令$X_i$为$A$的最后一个元素,否则令$X_i := -1$,然后按照以下格式打印它们:
$X_1$ $X_2$ $\ldots$ $X_Q$
样例输入1
11 ADD 3 SAVE 1 ADD 4 SAVE 2 LOAD 1 DELETE DELETE LOAD 2 SAVE 1 LOAD 3 LOAD 1
样例输出1
3 3 4 4 3 -1 -1 4 4 -1 4
最初,$A$是一个空序列,所以$A = ()$,笔记本的每一页上都记录了一个空序列。
- 在第1个查询中,$3$被添加到$A$的末尾,结果为$A = (3)$。
- 在第2个查询中,笔记本上第1页记录的序列变为$(3)$。仍然保持$A = (3)$。
- 在第3个查询中,$4$被添加到$A$的末尾,结果为$A = (3, 4)$。
- 在第4个查询中,笔记本上第2页记录的序列变为$(3, 4)$。仍然保持$A = (3, 4)$。
- 在第5个查询中,$A$被替换成记录在笔记本上第1页的$(3)$,结果为$A = (3)$。
- 在第6个查询中,$A$的最后一个项被删除,结果为$A = ()$。
- 在第7个查询中,由于$A$已经为空,什么也不发生。仍然保持$A = ()$。
- 在第8个查询中,$A$被替换成记录在笔记本上第2页的$(3,4)$,结果为$A = (3, 4)$。
- 在第9个查询中,笔记本上第1页记录的序列变为$(3, 4)$。仍然保持$A = (3, 4)$。
- 在第10个查询中,$A$被替换成记录在笔记本上第3页的$()$,结果为$A = ()$。
- 在第11个查询中,$A$被替换成记录在笔记本上第1页的$(3, 4)$,结果为$A = (3, 4)$。
样例输入2
21 ADD 4 ADD 3 DELETE ADD 10 LOAD 7 SAVE 5 SAVE 5 ADD 4 ADD 4 ADD 5 SAVE 5 ADD 2 DELETE ADD 1 SAVE 5 ADD 7 ADD 8 DELETE ADD 4 DELETE LOAD 5
样例输出2
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1