23486번 - 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$

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

• $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.

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