#2706. 「BalticOI 2015」文本编辑器

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

题目译自 BalticOI 2015 Day1 Editor(EDI),原题面见附加文件。
如欲转载翻译,请注明翻译者信息及转载出处。

Byteasar 是一个致力于编写革命性的文本编辑器的程序员。这个编辑器有两种操作,一种操作允许在编辑器中编辑文本,另一种允许撤销之前的操作。这个文本编辑器的一个创新特性是支持多级撤销操作。它如下工作。我们称文本编辑操作是 00 级操作。一个 ii 级的撤销操作(对于 i=1,2,i=1,2,\cdots)可以撤销最后一次级别最多为 i1i-1 且没有被撤销的操作。例如,一个级别为 11 的撤销操作只能撤销文本编辑操作,一个级别为 22 的撤销操作能撤销文本编辑操作和级别为 11 的撤销操作(但是不能撤销级别更高的操作了)。

更正式的,每一个已经出现的操作有两个状态:活动(active)或已撤销(undone)。设 XX 为一个操作。只有完成操作 XX 之后,它才处于活动状态。如果 XX 是一个 ii 级撤销操作,我们就要找到最近的一次处于活动状态的,最多为级别 i1i-1 的操作(用 X1X_1 表示),并把它(即 X1X_1)的状态变为已撤销。如果 X1X_1 也是一个撤销操作,我们必须把 X1X_1 撤销了的操作的状态变为活动(用 X2X_2 表示)。我们用相同的方式继续操作:无论何时我们撤销了之前撤销过 Xj+1X_{j+1} 的操作 XjX_j,我们必须改变 Xj+1X_{j+1} 操作的状态(当然,这将导致更多操作的状态变化)。整个状态修改链结束于一个编辑操作。

简单起见,目前编辑器中文本的内容用一个整数 ss 来表示,我们称之为编辑器状态(初始等于 00)。每一个编辑操作决定了它产生的编辑器状态。编辑器状态取决于最后一个活动的编辑操作。请帮助 Byteasar 写一个程序跟踪编辑器状态。

让我们在操作中理解这一过程:下表展示了一些 Byteasar 进行的操作和在操作之后的编辑器状态。Es\text{E}_s 表示一个把编辑器状态变为 ss 的编辑操作,Ui\text{U}_i 表示级别为 ii 的撤销操作。

操作 E1\text{E}_1 E2\text{E}_2 E5\text{E}_5 U1\text{U}_1 U1\text{U}_1 U3\text{U}_3 E4\text{E}_4 U2\text{U}_2 U1\text{U}_1 U1\text{U}_1 E1\text{E}_1
编辑器状态 00 11 22 55 22 11 22 44 22 11 00 11

首先,Byteasar 进行了三个编辑操作。编辑器状态从 00 变成 11,然后变成 22,最后变成 55。然后,它进行了两次级别为 11 的撤销操作,撤销了操作 E5\text{E}_5E2\text{E}_2(把它们的状态变为已撤销)。所以编辑器状态还原为 11。接下来的级别为 33 的撤销操作撤销了最后的操作 U1\text{U}_1(把它的状态变为已撤销),结果还原了操作 E2\text{E}_2(把它的状态还原为活动)。结果编辑器状态回到了 22。操作 U2\text{U}_2 撤销了操作 E4\text{E}_4,操作 U1\text{U}_1 又一次撤销已被还原的操作 E2\text{E}_2,最后的操作 U1\text{U}_1 撤销了操作 E1\text{E}_1,并且最后的操作是 E1\text{E}_1

输入格式

输入的第一行包含一个正整数 nn,表示 Byteasar 进行的操作数。接下来 nn 行包含一个对于操作的描述,一行一个,每一个操作是一个整数 aia_i。如果 ai>0a_i\gt 0,那么它表示一个编辑操作使得编辑器状态变为 aia_i。如果 ai<0a_i\lt 0,那么它表示一个级别为 ai-a_i 的撤销操作。你可以假设对于每一个撤销操作都会有一些级别较小且处于活动状态的操作可被撤销。

输出格式

你的程序需要输出 nn 行,第 ii 行应该包含一个整数,表示前 ii 个操作之后编辑器的状态。

样例

样例输入

11
1
2
5
-1
-1
-3
4
-2
-1
-1
1

样例输出

1
2
5
2
1
2
4
2
1
0
1

数据范围与提示

本题采用子任务式测评,只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务,1ain,n11\le |a_i|\le n,n\ge 1

对于每个子任务满足的条件如下:

子任务 条件 分数
11 n5×103n\le 5\times 10^3 2020
22 n3×105n\le 3\times 10^5,且只有操作 Ei\text{E}_iU1\text{U}_1 1515
33 n3×105n\le 3\times 10^5,且只有最后的一个数字参与评分(然而,前 n1n-1 个数必须是从 00nn 的一个整数) 2828
44 n3×105n\le 3\times 10^5 3737