COCI '14 Contest 3 #5 Stogovi

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 64M

Problem type

Mirko is playing with stacks. In the beginning of the game, he has an empty stack denoted with number $0$ ~0~. In the $i^{th}$ ~i^{th}~ step of the game he will choose an existing stack denoted with $v$ ~v~, copy it and do one of the following actions:

a. place number $i$ ~i~ on top of the new stack
b. remove the number from the top of the new stack
c. choose another stack denoted with $w$ ~w~ and count how many different numbers exist that are in the new stack and in the stack denoted with $w$ ~w~

The newly created stack is denoted with $i$ ~i~.

Mirko doesn't like to work with stacks so he wants you to write a programme that will do it for him. For each operation of type $b$ ~b~ output the number removed from stack and for each operation of type $c$ ~c~ count the required numbers and output how many of them there are.

Input

The first line of input contains the integer $N$ ~N~ $(1 \le N \le 300\,000)$ ~(1 \le N \le 300\,000)~, the number of steps in Mirko's game.

The steps of the game are chronologically denoted with the first $N$ ~N~ integers.

The $i^{th}$ ~i^{th}~ of the following $N$ ~N~ lines contains the description of the $i^{th}$ ~i^{th}~ step of the game in one of the following three forms:

a v for operation of type $a$ ~a~.
b v for operation of type $b$ ~b~.
c v w for operation of type $c$ ~c~.

The first character in the line denotes the type of operation and the following one or two denote the accompanying stack labels that will always be integers from the interval $[0, i-1]$ ~[0, i-1]~.

For each operation of type $b$ ~b~, the stack we're removing the element from will not be empty.

Output

For each operation type $b$ ~b~ or $c$ ~c~ output the required number, each in their own line, in the order the operations were given in the input.

Sample Input 1

5
a 0
a 1
b 2
c 2 3
b 4

Sample Output 1

2
1
2

Explanation for Sample Output 1

In the beginning, we have the stack $S_0 = \{\}$ ~S_0 = \{\}~. In the first step, we copy $S_0$ ~S_0~ and place number $1$ ~1~ on top, so $S_1 = \{1\}$ ~S_1 = \{1\}~. In the second step, we copy $S_1$ ~S_1~ and place $2$ ~2~ on top of it, $S_2 = \{1, 2\}$ ~S_2 = \{1, 2\}~. In the third step we copy $S_2$ ~S_2~ and remove number $2$ ~2~ from it, $S_3 = \{1\}$ ~S_3 = \{1\}~. In the fourth step we copy $S_2$ ~S_2~ and denote the copy with $S_4$ ~S_4~, then count the numbers appearing in the newly created stack $S_4$ ~S_4~ and stack $S_3$ ~S_3~, the only such number is number $1$ ~1~ so the solution is $1$ ~1~. In the fifth step we copy $S_4$ ~S_4~ and remove number $2$ ~2~ from it, $S_5 = \{1\}$ ~S_5 = \{1\}~.

Sample Input 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

Sample Output 2

Comments

18

Kirito commented on July 8, 2017, 4:38 p.m. ← edit 2 →

For future reference, the c query is poorly worded, it is asking for the number of distinct numbers that appear in stacks $S_u$ ~S_u~ and $S_v$ ~S_v~

E.g. is $S_u = \{1, 2\}$ ~S_u = \{1, 2\}~ and $S_v = \{1, 2, 3\}$ ~S_v = \{1, 2, 3\}~, the answer is $2$ ~2~, because $\{1, 2\}$ ~\{1, 2\}~ appear in both stacks.

2

fifiman commented on March 25, 2016, 8:41 a.m. ← edited →

Could someone explain the c operation. I'm having a tough time tying together the test data and explanation.

And for the explanation, shouldnt the first set be S0 = {1} instead of S1?