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^{t h}$ 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 \leq N \leq 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^{t h}$ of the following $N$ $N$ lines contains the description of the $i^{th}$ $i^{t h}$ 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

Copy

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

Sample Output 1

Copy

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

Copy

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

Copy

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?