#P4810. [COCI2014-2015#3] STOGOVI

[COCI2014-2015#3] STOGOVI

题目描述

译自 COCI 2014/2015 Contest 3 T5「STOGOVI」

Mirko 正在玩栈。游戏开始时,他有一个编号为 00 的空栈。在游戏中的第 ii 步,他会选择一个存在的编号为 vv 的栈,将它复制一份并进行以下其中一种操作:

  1. 将数字 ii 加入新栈的顶部。

  2. 将新栈顶部的数字删除。

  3. 选择另外一个编号为 ww 的栈,并统计有多少个不同的数同时存在于新栈与栈 ww 中。

新创建的栈编号为 ii

Mirko 不喜欢自己用栈模拟这个过程,所以他想要你替他写一个程序来执行这个过程。对于每个删除操作输出删除的数,且对于每个统计操作,输出统计的结果。

输入格式

第一行,一个整数 N(1N300 000)N(1 \le N \le 300\ 000),表示这局游戏的步数。

游戏的步骤以时间顺序按前 NN 个整数编号。

以下 NN 行,第 ii 行表示游戏的第 ii 步,为以下三种格式之一:

  • a v,表示加入操作。

  • b v,表示删除操作。

  • c v w,表示统计操作。

操作所涉及的编号一定在 [0,i1][0,i-1] 中。

保证删除操作不会操作空栈。

输出格式

对于每个删除或统计操作,输出一行,表示请求的数字。按照输入文件给出的操作顺序排列。

5
a 0
a 1
b 2
c 2 3
b 4
2
1
2
11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8
2
2
8
8

提示

样例解释 1

开始时,我们有栈 S0={}S_0 = \{\}

第一步,我们复制 S0S_0 并将数字 11 加入到顶部,S1={1}S_1 = \{1\}

第二步,我们复制 S1S_1 并将数字 22 加入到顶部,S2={1,2}S_2 = \{1,2\}

第三步,我们复制 S2S_2 并删除数字,22S3={1}S_3 = \{1\}

第四步,我们复制 S2S_2 并编号为 S4S_4,统计有多少个不同的数同时存在于 S4S_4S3S_3 中。唯一同时存在于两个栈中的数是 11,所以答案为 11

第五步,我们复制 S4S_4 并删除数字,22S5={1}S_5 = \{1\}