P4511 [CTSC2015] Schedule Management

Youxiang is a very influential person in Gensokyo. She handles a huge number of affairs every day, and it has become hard for her to manage them all. Therefore, she decides to develop a schedule management program to help manage her tasks. For each task $i$, there is a deadline $t_i$ and a profit $p_i$. If Youxiang finishes this task no later than day $t_i$, she will obtain a profit of $p_i$. Youxiang is very capable and can finish any task in exactly one day. However, since there are so many tasks, she cannot always complete all of them. She wants to know, in such cases, what the maximum total profit she can obtain is. Since people in Gensokyo are fickle, tasks keep changing. Youxiang wants this management program to support inserting a task and deleting a task. Specifically, the program should support the following 2 operations: 1. `ADD t p`: Insert a new task with deadline $t$ and profit $p$. 2. `DEL t p`: Delete one task with deadline $t$ and profit $p$. If multiple such tasks exist, delete exactly one. It is guaranteed that such a task exists. After each operation is executed, you need to output the maximum total profit achievable by completing tasks. Youxiang has $T$ days to schedule, from day $1$ to day $T$. Can you help her write this efficient program?

The first line contains two integers $T$ and $Q$, denoting the number of days and the number of operations. The next $Q$ lines describe the operations. The $i$-th line is the $i$-th operation, in the form `ADD t p` or `DEL t p`, with meanings as described above.

For each operation, output one integer: the maximum total profit Youxiang can obtain after that operation is performed.

It is guaranteed that $1 \le T, Q \le 3 \times 10^5$. $\text{Statement fixed by @Starrykiller.}$ Translated by ChatGPT 5