← 返回题目列表

AtCoder · abc273_e

H. 笔记本

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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

你被给予 Q 查询。 每个查询属于以下四种类型之一:

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.

最初, 黑板上写着 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,让 X_i 是最后一个元素 A 处理后 i-第一个查询,或者让 X_i := -1 if A 为空,按以下格式打印:

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-st 查询, 3 附加到尾部 A,导致 A = (3).
  • 由 2-nd查询,记录在 1笔记本的第页变为 (3)。 仍然是 A = (3).
  • 由 3-rd 查询, 4 附加到尾部 A,导致 A = (3, 4).
  • 由 4第一个查询,记录在 2笔记本的第页变成 (3, 4)。 仍然是 A = (3, 4).
  • 由 5第一个查询, A 被替换为 (3),记录在 1- 笔记本的第页,导致 A = (3).
  • 由 6第一个查询,最后一项 A 被删除,导致 A = ().
  • 由 7-th 查询,没有任何反应,因为 A 已为空。 仍然是 A = ().
  • 由 8第一个查询, A 被替换为 (3,4),记录在 2- 笔记本的第 3 页,导致 A = (3, 4).
  • 由 9第一个查询,记录在 1笔记本的第页变为 (3, 4)。 仍然是 A = (3, 4).
  • 由 10第一个查询, A 被替换为 (),记录在 3- 笔记本的第一页,导致 A = ().
  • 由 11第一个查询, A 被替换为 (3, 4),记录在 1- 笔记本的第页,导致 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