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

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

题目描述

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

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

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

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

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

操作 E1\text{E}_1E1 E2\text{E}_2E2 E5\text{E}_5E5 U1\text{U}_1U1 U1\text{U}_1U1 U3\text{U}_3U3 E4\text{E}_4E4 U2\text{U}_2U2 U1\text{U}_1U1 U1\text{U}_1U1 E1\text{E}_1E1
编辑器状态 000 111 222 555 222 111 222 444 222 111 000 111

首先,Byteasar 进行了三个编辑操作。编辑器状态从 000 变成 111,然后变成 222,最后变成 555。然后,它进行了两次级别为 111 的撤销操作,撤销了操作 E5\text{E}_5E5E2\text{E}_2E2(把它们的状态变为已撤销)。所以编辑器状态还原为 111。接下来的级别为 333 的撤销操作撤销了最后的操作 U1\text{U}_1U1(把它的状态变为已撤销),结果还原了操作 E2\text{E}_2E2(把它的状态还原为活动)。结果编辑器状态回到了 222。操作 U2\text{U}_2U2 撤销了操作 E4\text{E}_4E4,操作 U1\text{U}_1U1 又一次撤销已被还原的操作 E2\text{E}_2E2,最后的操作 U1\text{U}_1U1 撤销了操作 E1\text{E}_1E1,并且最后的操作是 E1\text{E}_1E1

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

1
2
5
2
1
2
4
2
1
0
1

数据范围与提示

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

对于全部子任务,1≤∣ai∣≤n,n≥11\le |a_i|\le n,n\ge 11ain,n1

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

子任务 条件 分数
111 n≤5×103n\le 5\times 10^3n5×103 202020
222 n≤3×105n\le 3\times 10^5n3×105,且只有操作 Ei\text{E}_iEiU1\text{U}_1U1 151515
333 n≤3×105n\le 3\times 10^5n3×105,且只有最后的一个数字参与评分(然而,前 n−1n-1n1 个数必须是从 000nnn 的一个整数) 282828
444 n≤3×105n\le 3\times 10^5n3×105 373737