406871: GYM102586 K Game and Queries

Alice and Bob are going to play a game. The rule of the game is as follows:

• There are some monsters, each of which has a specified HP.
• Alice and Bob take turns alternately, with Alice going first.
• In Alice's turn, she chooses one of the monsters and increases its HP by $$$1$$$.
• In Bob's turn, he chooses one of the monsters and decreases its HP by $$$2$$$. If the monster's HP becomes $$$0$$$ or less, the monster disappears.
• The game ends when $$$k$$$ monsters disappear.

Alice's objective is to finish the game as late as possible, while Bob's is as soon as possible.

Initially, there are no monsters. You have to process $$$Q$$$ queries of the following types:

• Type $$$1$$$: You are given two integers $$$X_i$$$ and $$$Y_i$$$. After this query, the number of monsters whose HPs are $$$X_i$$$ becomes $$$Y_i$$$.
• Type $$$2$$$: Given an integer $$$K_i$$$, calculate how many turns would Bob take if the game started with current monsters and $$$k=K_i$$$, assuming both players play optimally.

Note that the game doesn't happen in reality, and the monsters don't disappear.

Input is given from Standard Input in the following format:

$$$Q$$$

Description of the $$$1$$$-st query

Description of the $$$2$$$-nd query

$$$\vdots$$$

Description of the $$$Q$$$-th query

The description of each query is in one of the following formats:

Type $$$1$$$

$$$1$$$ $$$X_i$$$ $$$Y_i$$$

Type $$$2$$$

$$$2$$$ $$$K_i$$$

Constraints:

• $$$1 \leq Q \leq 3 \times 10^5$$$
• $$$1 \leq T_i \leq 2$$$
• $$$1 \leq X_i \leq 10^6$$$
• $$$0 \leq Y_i \leq 10^6$$$
• $$$1 \leq K_i \leq ($$$ the number of current monsters $$$)$$$
• There is at least one query of the type $$$2$$$
• All values in input are integers.

For each query of the type $$$2$$$, print the answer in a line.

6
1 1 4
2 3
1 2 3
2 6
1 2 2
2 6

3
7
8

20
1 1 12
2 12
1 2 15
2 12
2 3
1 12 10
2 27
1 14 6
2 7
2 43
2 22
1 8 7
1 1 11
2 49
1 5 19
2 38
2 8
1 12 14
1 16 1
2 24

12
12
3
42
7
246
25
301
91
8
32

In the example $$$1$$$, after the $$$5$$$-th query, there are $$$4$$$ monsters whose HPs are $$$1$$$ and $$$2$$$ monsters whose HPs are $$$2$$$.