Corrections to a series
A climatologist is homogenising a series of daily temperatures. When a weather station is moved or an instrument on it replaced, a jump unrelated to the weather appears in the series, and all the readings for the period before or after the change are shifted by a correction. Corrections come one after another, and between them colleagues need answers: which day of a period was the coldest and which the warmest, taking into account all the corrections made by that moment.
Two tests are the real daily mean temperature of Almaty from 1 January 1941 to 31 December 2025 in tenths of a degree, 31,046 days: in one, corrections to years and decades are mixed with questions about winters, summers and random periods; in the other there are only questions.
Input
The first line holds n and q (1 ≤ n ≤ 100,000, 1 ≤ q ≤ 50,000). The second holds n integers a1, …, an, |ai| ≤ 10⁹. Then q lines, each with one operation:
+ l r d: add d to each of the numbers al, …, ar (|d| ≤ 10⁹);? l r: a question about the numbers al, …, ar.
Everywhere 1 ≤ l ≤ r ≤ n.
Output
For each question, a line of two numbers separated by a space: the smallest and the largest of al, …, ar, taking into account all the corrections made before this question.
Examples
Example 1
16 6 -21 -10 -16 -72 -115 -133 -154 -191 -182 -116 -68 -68 -99 -88 -62 -67 ? 6 9 + 4 13 50 ? 6 9 ? 1 16 + 1 8 -10 ? 4 5
-191 -133 -141 -83 -141 -10 -75 -32
Example 2
1 4 7 ? 1 1 + 1 1 -3 + 1 1 -3 ? 1 1
7 7 1 1
Limits
- Time · Python
- 15000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Without corrections a sparse table or a segment tree would be enough. If corrections touched one day, the tree would change a leaf and the path to the root. A range correction is thousands of leaves. Does every one of them need to know?
2Hint 2
Adding to all the days of a node shifts its minimum and maximum by the same amount; the children need not be asked. A node lying entirely within the correction’s range can fix its answer at once and leave its children a note.
3The idea
A segment tree with deferred corrections. A node holds the minimum and maximum of its days and a note “add d” for its children. A correction descends like a query: to a node entirely inside, add d to the minimum, maximum and note, and do not go down; pass through a partially touched node, first handing its note to the children, and on the way back recompute its minimum and maximum from the children. A question descends the same way, also handing notes down on its path. Both operations visit at most four nodes per level, O(log n).
4Walkthrough
The Go solution is the recursive tree from the article, only with a single note, “add”. Notes glue by addition: two additions in a row are one addition of the sum, so the order does not matter here.
The Python solution works without recursion: in Python a recursive descent is several times slower than a loop. The leaves lie in cells n…2n − 1, and the parent of cell i is cell i/2. A correction walks the range bottom-up, like a bottom-up tree’s query, and adds d to each node it takes: to the minimum, maximum and note d[i]. Then the ancestors of the two extreme leaves are recomputed: a node’s minimum is the smaller of its children’s minima plus its own note, since the note applies to the whole subtree. Before a question, the notes on the paths from the root to the two extreme leaves are pushed down from the top; after that the answers of all the nodes the question will take are correct.
4+Solution
5Complexity
Building is O(n), each operation O(log n), O(n + q log n) time and O(n) memory in all. The direct approach, a loop over the correction’s days and a slice for a question, costs O(n) per operation: the fourth test has 50,000 operations on ranges tens of thousands long.
6Common mistakes
- A loop over the correction’s days. Correct, but O(n·q): corrections to decades are thousands of days each.
- Forgetting to push the note down in a question. A node the question descends through must hand its note to its children, otherwise their answers are stale. On small tests this often goes unnoticed.
- In the bottom-up version, forgetting a node’s own note when recomputing. A node’s minimum is min(children) +
d[i], not just min(children): the note has not yet been handed down. - 32-bit numbers. Values up to 10⁹ and up to 50,000 corrections of 10⁹ give numbers of the order of 5·10¹³; the seventh test checks this.