Background

CTT2021 D1T2

Problem Description

Byte Game Company has recently released a new game, Magic Tower Online. Players can control a hero to fight monsters in the game world. When the game was first released, there were no monsters in the magic tower. Then, $q$ events will happen one by one, and each event is one of the following three types:

• + x y z a b: This means a new version of the game is released, and a new monster is added into the game. If this is the first monster added, then its ID is $1$; otherwise, its ID is the ID of the last added monster $+ 1$. This monster is located on floor $x$ of the magic tower, its level is $y$, and its difficulty is $z$. If the player chooses to kill this monster, it costs $a$ HP. After killing it successfully, the player will obtain a potion that can restore $b$ HP and use it immediately.
• - k: This means a new version of the game is released, and the monster with ID $k$ is removed due to balance issues, so it will no longer appear in the magic tower. Note: removed monsters still keep their IDs, and monsters added in the future will not reuse the IDs of removed monsters.
• ? g l d: This is a query. A player wants to kill all monsters among the first $g$ floors of the magic tower whose level is at most $l$ and difficulty is at most $d$. The player may kill these monsters in any order. Moving up to a new floor does not require killing all monsters on the current floor, and the battle process will not be affected by other monsters. Your task is to help the player compute the minimum initial HP the hero needs before setting out. If at any moment the hero's HP becomes negative, the game ends, and you must prevent this from happening.

Write a program to answer each query in order. Note that each query is only the player's thought experiment and will not actually kill any monster.

Input Format

The first line contains an integer $q$, representing the number of events.

The next $q$ lines each start with a character, followed by several integers, describing each event in order.

The input guarantees $1\leq q\leq 150\,000$, the total number of monsters does not exceed $50\,000$, and the number of queries does not exceed $50\,000$.

For the add-monster operation, it is guaranteed that $1\leq x,y,z\leq 10\,000$, and $0\leq a,b\leq 10^9$.

For the remove-monster operation, it is guaranteed that the operation is valid, and each monster will not be removed repeatedly.

For queries, it is guaranteed that $1\leq g,l,d\leq 10\,000$.

Output Format

For each query, output one line with one integer, which is the minimum initial HP of the hero before setting out.

10
+ 2 1 1 3 4
+ 1 2 2 2 5
? 2 2 2
+ 1 1 1 8 2
? 2 2 1
? 1 2 2
- 1
? 2 2 2
- 3
? 1 2 2

2
7
5
5
2

Hint

1. (3 points) The total number of monsters does not exceed $8$, and the number of queries does not exceed $8$.
2. (7 points) The total number of monsters does not exceed $5\,000$, and the number of queries does not exceed $5\,000$.
3. (10 points) Potions do not restore HP, and the difficulty of all monsters is $1$. That is, $b=0$, and $z=d=1$.
4. (17 points) $1\leq x,y,z,g,l,d\leq 5$.
5. (30 points) The level and difficulty of all monsters are $1$. That is, $y=z=l=d=1$.
6. (33 points) No additional constraints.

Translated by ChatGPT 5