Score : $500$ points

问题描述

我们有一个整数序列 $A$ 和一本笔记本。该笔记本有 $10^9$ 页。

你将收到 $Q$ 个查询请求。每个查询请求属于以下四种类型之一：

ADD $x$: 将整数 $x$ 添加到序列 $A$ 的末尾。

DELETE: 若 $A$ 不为空，则删除 $A$ 的最后一个元素；否则不做任何操作。

SAVE $y$: 擦除笔记本上第 $y$ 页记录的序列，并将当前的 $A$ 序列记录到第 $y$ 页。

LOAD $z$: 用笔记本上第 $z$ 页记录的序列替换当前的 $A$ 序列。

初始时，序列 $A$ 是空的，且笔记本的每一页都记录着一个空序列。按照给定顺序依次处理这 $Q$ 个查询请求，并在处理完每个查询后打印出 $A$ 的最后一个元素。

由于输入和输出可能较大，建议使用快速输入输出方法。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 11:30:41