The first frost
An agronomist planning the harvest asks the same thing for every year: when, after 1 August, did a day with a mean daily temperature no higher than a given threshold (zero, minus five, minus ten degrees) first occur? The series is not frozen meanwhile. When a sensor breaks, the damaged stretch of the series is filled with a single value, the norm for that season, and such replacements arrive mixed with the questions.
One of the tests is the real daily mean temperature of Almaty from 1 January 1941 to 31 December 2025 in tenths of a degree, 31,046 days. Some thresholds in it are colder than any day of the series.
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 x: assign x to each of the numbers al, …, ar (1 ≤ l ≤ r ≤ n, |x| ≤ 10⁹);? l t: find the smallest i ≥ l for which ai ≤ t (1 ≤ l ≤ n, |t| ≤ 2·10⁹).
Output
For each question, a line with the number i found, or −1 if there is no such day.
Examples
Example 1
16 6 -21 -10 -16 -72 -115 -133 -154 -191 -182 -116 -68 -68 -99 -88 -62 -67 ? 1 -150 = 5 9 0 ? 1 -150 ? 3 -100 ? 11 -68 ? 16 -68
7 -1 10 11 -1
Example 2
1 4 5 ? 1 5 ? 1 4 = 1 1 -5 ? 1 4
1 -1 1
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 8 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
Walking the days from l until a cold one appears is simple, but if there is no cold day right to the end, the walk is as long as the whole series. What do you need to know about a whole piece of the series to see that there is no cold day in it?
2Hint 2
The minimum. If a piece’s minimum is above the threshold, the whole piece can be skipped. A segment tree stores the minimum for pieces of all sizes, and a search can go down it from the top, like the descent in the article. What remains is replacing a range with a single value.
3Hint 3
Replacing all the days of a node with one number x makes the node’s minimum equal to x; the children need not be asked. That is a note “assign x”, which the node hands to its children when someone passes through it.
4The idea
A segment tree with the minimum in its nodes and deferred assignment. Replacing a range lays notes on O(log n) nodes. A question is a descent: a node that ends before l or whose minimum is above t is skipped entirely; otherwise, having handed its note to the children, search first in the left child, then in the right. The leaf you reach is the answer.
5Walkthrough
The Go solution is the recursive descent from the article. Why it is fast: a failed visit to a node whose minimum is no higher than t but all such days are left of l is possible only for nodes containing l inside, one per level. A node lying entirely to the right of l with a minimum no higher than t certainly contains the answer, and from it the descent goes along a single path to a leaf. In total O(log n) nodes.
The Python solution works without recursion, over a tree of 2k leaves: the extra leaves are plus infinity and are never colder than the threshold. First the notes on the path from the root to leaf l are pushed down. Then the search goes over the blocks that make up the range [l, end): from leaf l upwards while the node is a left child, then right to the neighbour. Each such block is the right neighbour of a node on the path to l, and there are no notes above it any more. As soon as a block’s minimum is no higher than t, descend into it: into the left child if its minimum is no higher than t, otherwise into the right, pushing notes down on the way.
Replacing a range is also done without recursion: the notes on the paths to the two ends are pushed down from the top, the range is walked bottom-up, the nodes taken get the value and a note, and then the ancestors of the two ends are recomputed bottom-up.
5+Solution
6Complexity
Building is O(n), each replacement and each question O(log n). Walking the days costs O(n) per question, and tests with a threshold colder than the whole series turn it into q·n, billions of steps. Replacing by slice is fast in Python, in C; it is the searching that is slow.
7Common mistakes
- Walking the days from l. On real weather it often finds the answer within a few weeks and seems fast. But a threshold colder than the whole series, or a long warm autumn, forces it to the end.
- Binary search on the answer with a minimum query on [l, m]. Correct, but O(log² n) per question: it works, though several times slower than the descent.
- Forgetting to push the note down during the descent. A node with an “assign” note knows its minimum, but its children do not yet: descending into the children without pushing finds an old cold day that no longer exists.
- A non-strict comparison. A day no higher than the threshold is needed, ai ≤ t: in the first example day 11 equals the threshold −68 and qualifies, while day 16, −67, does not.