레이팅 미적용People in southern Sweden are known to eat falafel a lot. The price of falafel is highly volatile, and the best way to analyze the state of the economy is to go to the same falafel place every day and add up all the prices on their menu.
A falafel place has \(N\) different dishes on their menu. The \(i\)th dish has price \(p_i\).
Every day, one of the following events happen:
- |INFLATION x|: The integer \(x\) is added to all prices.
- |SET x y|: Every dish with price \(x\) gets its price set to \(y\).
Your task is to process \(Q\) days, and after each day print the sum of all prices \(p_i\).
(An illustrative figure from the official statement is omitted here.)
- \(1 \leq N \leq 3 \cdot 10^5\).
- \(1 \leq p_i \leq 10^6\) (for each \(i\) such that \(1 \leq i \leq N\)).
- \(1 \leq Q \leq 10^5\).
- \(1 \leq x,y \leq 10^6\) for all days.
Note: The answer may not fit in a \(32\)-bit integer, so be aware of overflows if you are using C++.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
Group | Score | Limits 1 | 14 | \(N=1\) 2 | 28 | \(N, Q, p_i, x, y \leq 100\) 3 | 19 | There are only |INFLATION| events 4 | 23 | There are only |SET| events 5 | 16 | No additional constraints
The first line contains one integer \(N\), the number of dishes.
The second line contains \(N\) integers \(p_1, p_2, \ldots, p_N\).
The third line contains one integer \(Q\), the number of days.
The following \(Q\) lines each contain a string \(s\) followed by either one or two integers.
If \(s\) is |INFLATION|, then one integer \(x\) follows. This means that \(x\) is added to all prices on this day.
If \(s\) is |SET|, then two integers \(x\) and \(y\) follow. This means that all dishes with price \(x\) get their price set to \(y\) on this day.
Print \(Q\) lines, the sum of all prices \(p_i\) after each day.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 14점 | None |
Subtask 2 | 28점 | None |
Subtask 3 | 19점 | None |
Subtask 4 | 23점 | None |
Subtask 5 | 16점 | None |
5
2 1 1 2 5
6
INFLATION 1
SET 3 2
SET 5 2
INFLATION 4
SET 6 1
SET 10 1
16
14
14
34
14
5
3
1 4 1
5
SET 1 1
SET 3 4
INFLATION 2
SET 3 1
SET 6 4
6
6
12
8
6