AT_abc273_e [ABC273E] Notebook

题目描述

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

给定 $Q$ 个操作，每个操作属于以下四种之一：

ADD $x$ ：将整数 $x$ 添加到 $A$ 的末尾。

DELETE ：删除 $A$ 的末尾元素。如果 $A$ 为空，则什么也不做。

SAVE $y$ ：将第 $y$ 页上的序列擦除，并将当前的 $A$ 写入第 $y$ 页。

LOAD $z$ ：用笔记本第 $z$ 页上的序列替换 $A$。

初始时，$A$ 是空序列，笔记本的所有页面上都写着空序列。从这个初始状态开始，依次执行 $Q$ 个操作，并在每个操作执行后，输出 $A$ 的末尾元素。

如果输入输出量较大，建议使用高效的输入输出方法。

输入格式

输入通过标准输入按以下格式给出。

$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

输入 #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

输入输出样例 #2

输入 #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

说明/提示

约束

• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq x, y, z \leq 10^9$
• $Q, x, y, z$ 均为整数
• 所有操作均为上述四种之一

样例解释 1

初始时，$A$ 是空序列，即 $A=()$，笔记本所有页面上都写着空序列。

• 第 $1$ 个操作，将 $3$ 添加到 $A$ 的末尾，$A=(3)$。
• 第 $2$ 个操作，将 $A$ 写入笔记本第 $1$ 页，此时第 $1$ 页内容为 $(3)$，$A$ 不变。
• 第 $3$ 个操作，将 $4$ 添加到 $A$ 的末尾，$A=(3,4)$。
• 第 $4$ 个操作，将 $A$ 写入笔记本第 $2$ 页，此时第 $2$ 页内容为 $(3,4)$，$A$ 不变。
• 第 $5$ 个操作，用笔记本第 $1$ 页的内容 $(3)$ 替换 $A$，$A=(3)$。
• 第 $6$ 个操作，删除 $A$ 的末尾元素，$A=()$。
• 第 $7$ 个操作，$A$ 已为空，什么也不做，$A=()$。
• 第 $8$ 个操作，用笔记本第 $2$ 页的内容 $(3,4)$ 替换 $A$，$A=(3,4)$。
• 第 $9$ 个操作，将 $A$ 写入笔记本第 $1$ 页，此时第 $1$ 页内容为 $(3,4)$，$A$ 不变。
• 第 $10$ 个操作，用笔记本第 $3$ 页的内容 $()$ 替换 $A$，$A=()$。
• 第 $11$ 个操作，用笔记本第 $1$ 页的内容 $(3,4)$ 替换 $A$，$A=(3,4)$。

由 ChatGPT 4.1 翻译