Loading...
Loading...
Loading...
A college stationery shop writes down its net sales (in rupees) for n days. A day with more refunds than sales has a negative value.
The accountant then works through q lines, in order. A line sum l r asks for the total of days l to r, both included. A line set i x corrects day i, so its value becomes x. Every later sum must use the corrected values.
Print the answer to every sum line.
sum l r or set i x.sum line, in order: the total of days l to r at that moment.sum line.Example
Input
5 6 3 -1 4 1 5 sum 1 5 set 2 6 sum 1 3 set 2 2 sum 2 4 sum 4 4
Output
12 13 7 1
Days 1–5: 3 − 1 + 4 + 1 + 5 = 12. Day 2 becomes 6, so days 1–3 give 3 + 6 + 4 = 13. Day 2 then becomes 2, so days 2–4 give 2 + 4 + 1 = 7. Day 4 alone is 1.
Try the problem first. Open one hint at a time.
Adding the days again for every sum costs up to n steps, which is 4 × 10^10 steps in the worst case.
A plain running-total array answers a sum fast, but one correction near the start changes almost all of it.
Use a binary indexed tree (Fenwick tree): each cell holds the total of a block of days whose length is a power of two. A running total and a correction each touch only about log n cells.
A set is a change by x minus the current value. Keep the current values in their own array so you know that difference, and use long for the totals.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor