Analyzing Contracts
本题没有可用的提交语言。
Description
Doctor Kruskal is starting a tiberium trading business. They have $N$ possible suppliers of tiberium, and many clients interested in receiving tiberium to run their own industries.
Calendar days are numbered chronologically using positive integers, and each supplier is identified by a distinct integer from $1$ to $N$. Supplier $i$ can supply tiberium on any day from day $S_i$ onwards, but not on the days strictly before $S_i$. They charge a price of $P_i$ dollars per day for such a service. Since Kruskal is very smart, the list of suppliers contains only the best suppliers in the city. Besides, it is the case that $S_i < S_{i+1}$ and $P_i > P_{i+1}$ for ${i}={1}, {2}, \ldots, {N-1}$.
Kruskal's system keeps a database of available clients. Initially, this database is empty and contains no clients. Clients will be arriving one by one, and each of them is immediately added to the database upon arrival. The $j$-th client is interested in receiving tiberium on any day up to day $E_j$ inclusive. For each day that they receive tiberium, their industry will generate $R_j$ dollars of gross revenue. Thus, if Kruskal matches supplier $i$ to client $j$, the final profit of this whole operation after deducting the tiberium cost will be $(R_j - P_i) \times (E_j - S_i + 1)$, where $S_i \leq E_j$, as otherwise no tiberium could be provided.
At any moment, Kruskal's system can quickly compute, for any particular supplier $i$, the optimal client among those in the database, so that the profit of the operation when matching the supplier and the client is maximized, and it can report such maximum profit. It might be the case that a positive profit for a supplier cannot be achieved with any of the available clients; in that case, the system reports a profit of zero.
Notice that when Kruskal's system is requested to compute the maximum profit for a given supplier, that supplier is matched with at most one of the available clients, and in that case, such a match has no effect at all on future operations. This means that both the supplier and the client can be considered again for future matchings.
Your task is to implement Kruskal's system.
The first line contains an integer $N$ ($1 \leq N \leq 2 \times 10^5$) indicating the number of suppliers.
The $i$-th of the next $N$ lines describes supplier $i$ with two integers $S_i$ and $P_i$ ($1 \leq S_i, P_i \leq 10^9$), denoting respectively the start day and the price per day for the supplier. It is guaranteed that $S_i < S_{i+1}$ and $P_i > P_{i+1}$ for ${i}={1}, {2}, \ldots, {N-1}$.
The next line contains an integer $Q$ ($1 \leq Q \leq 2 \times 10^5$) representing the number of operations that must be processed. Operations are described in the next $Q$ lines, in the order they are executed in the system, one operation per line. There are two types of operations.
If the operation adds a client to the database, the line contains the lowercase letter "c", followed by two integers $E$ and $R$ ($1 \leq E, R \leq 10^9$), indicating respectively the end day and the gross revenue per day for the client.
If the operation requests to compute the maximum profit for a supplier, the line contains the lowercase letter "s", followed by an integer $I$ ($1 \le I \le N$) that identifies the supplier. It is guaranteed that the input contains at least one operation of this type.
Output a line for each operation of type "s". The line must contain an integer indicating the maximum possible profit when matching an available client with the given supplier. Write the results of the operations in the order they appear in the input.
Input
The first line contains an integer $N$ ($1 \leq N \leq 2 \times 10^5$) indicating the number of suppliers.
The $i$-th of the next $N$ lines describes supplier $i$ with two integers $S_i$ and $P_i$ ($1 \leq S_i, P_i \leq 10^9$), denoting respectively the start day and the price per day for the supplier. It is guaranteed that $S_i < S_{i+1}$ and $P_i > P_{i+1}$ for ${i}={1}, {2}, \ldots, {N-1}$.
The next line contains an integer $Q$ ($1 \leq Q \leq 2 \times 10^5$) representing the number of operations that must be processed. Operations are described in the next $Q$ lines, in the order they are executed in the system, one operation per line. There are two types of operations.
If the operation adds a client to the database, the line contains the lowercase letter "c", followed by two integers $E$ and $R$ ($1 \leq E, R \leq 10^9$), indicating respectively the end day and the gross revenue per day for the client.
If the operation requests to compute the maximum profit for a supplier, the line contains the lowercase letter "s", followed by an integer $I$ ($1 \le I \le N$) that identifies the supplier. It is guaranteed that the input contains at least one operation of this type.
Output
Output a line for each operation of type "s". The line must contain an integer indicating the maximum possible profit when matching an available client with the given supplier. Write the results of the operations in the order they appear in the input.
4
2 8
4 5
7 3
9 2
11
s 1
c 10 10
s 1
s 2
s 3
s 4
c 7 26
s 2
s 4
s 3
s 1
0
18
35
28
16
84
16
28
108