Notebook

题目描述

我们有一个整数序列 $A$ 和一本笔记本。 这本笔记本有 $10^9$ 页。 给出 $Q$ 个查询。 每个查询是下列四类之一： ADD $x$：在 $A$ 的末尾追加一个整数 $x$。

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$，令 $X_i$ 为处理到第 $i$ 个查询后 $A$ 的最后一个元素，如果 $A$ 为空则令 $X_i := -1$，并按以下格式输出它们： $X_1$ $X_2$ $\ldots$ $X_Q$

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

3 3 4 4 3 -1 -1 4 4 -1 4

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

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$ 都是整数。 给定的每个查询都是问题描述中的四类之一。最初，$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)$。

标签: AtCoder|abc273E

来源

AtCoder|abc273E