The hottest day
A weather information service answers questions of the form “when was it hottest from such-and-such a day to such-and-such”: which day of the period was the hottest by daily mean temperature. If there are several such days, the earliest is named. The series does not change, and there are tens of thousands of 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, with questions about years, summers, decades and random periods.
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 with numbers l and r (1 ≤ l ≤ r ≤ n).
Output
For each question, a line with the smallest i in [l, r] for which ai is the largest of al, …, ar.
Examples
Example 1
16 5 231 261 264 255 223 217 220 212 217 226 241 266 299 313 282 271 3 14 1 4 5 10 16 16 2 3
14 3 10 16 3
Example 2
5 4 5 7 7 1 7 1 5 3 5 4 4 4 5
2 3 4 5
Limits
- Time · Python
- 6000 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
The series does not change and there are many questions: a sparse table fits, the maximum of any range in two reads. But what is needed is not the maximum but the day where it is reached, and the earliest one. Can the table store a day rather than a temperature?
2Hint 2
The table works if the gluing is associative, commutative and unharmed by repetition. Check whether that holds for the rule “the better day is the hotter one, and on a tie the earlier one”.
3The idea
The rule “hotter, and on a tie earlier” is a maximum over the pair (temperature, −day number): different days have different pairs, and from any set of days the rule picks exactly one. So it is an ordinary maximum, only by a different key, and the overlap of two blocks does it no harm. Build the table over day numbers with this rule and answer a question with two cells of row ⌊log₂(r − l + 1)⌋.
4Walkthrough
In Go the table stores day numbers, and the function better compares them by temperature and by number. In Python it is convenient to pack each pair into one number: (t + 10⁹)·217 + (217 − 1 − i). The temperature takes the high digits and the day number the low ones, reversed, so that of two equal temperatures the earlier day has the larger key. Then each row of the table is built with one call to map(max, …) over two shifted slices of the previous row, and the day number comes out of the low 17 bits of the answer. 217 = 131,072 is larger than any n, so the numbers do not run into the temperature.
4+Solution
5Complexity
Building takes O(n log n) time and memory, each question O(1). For a hundred thousand days that is 17 table rows. Scanning the range for each question is O(n): in the fourth test there are 50,000 questions about almost the whole series.
6Common mistakes
- A slice and
maxfor each question. Fast on short periods, but O(r − l), and questions about decades are thousands of days each. - Storing only the temperature in the table. The maximum is found but the day is not; looking for it afterwards with a pass over the range is O(n) again.
- The wrong day on a tie. If only temperature is compared, either of two equal days may be picked. In the second example the answer to the first question is 2, not 3 or 5; in the sixth test all days are equal, and the answer is always l.
- A floating-point logarithm. For lengths up to 10⁵
floor(log2(L))is correct, but the habit is dangerous: starting from 2⁴⁹ − 1, the logarithm of a number just below a power of two rounds up to an integer, and the table row comes out one too high. The position of the highest bit is safer to compute with integers:bit_length() − 1orbits.Len − 1.