The median of a period
A weather archive stores the mean temperature for each of n days. Climatologists need not means but order statistics: the median of a month, the coldest day of a summer, the tenth warmest day of a period. Each question “what is the k-th smallest temperature among the days from the l-th to the r-th” must be answered quickly: there are tens of thousands of questions.
Three tests are the real archive: the mean temperature of Almaty for each day of 1941–2025 from the ERA5 reanalysis, in tenths of a degree. In one of them the median of every month and every summer is asked.
In the example, for all seven days in increasing order: −40, −10, 10, 20, 20, 30, 50, and the fourth is 20. From the second to the fifth day the coldest is −10; the third day is alone, and its temperature is 50; from the fourth to the seventh the second smallest is 10.
Input
The first line holds n and q (1 ≤ n, q ≤ 40,000). The second holds n integer temperatures of absolute value at most 109. Then q lines of three integers l, r, k (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ r − l + 1).
Output
For each question, the k-th smallest temperature among the days from the l-th to the r-th, one per line.
Examples
Example 1
7 4 30 -10 50 20 20 -40 10 1 7 4 2 5 1 3 3 1 4 7 2
20 -10 50 10
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 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
If a period always began on the first day, a segment tree over values would be enough: a node holds how many days fell into its range of temperatures, and the k-th is found by descending from the root. How do you get from “the first r days” to “the days from the l-th to the r-th”?
2Hint 2
The number of days of the period in a range of temperatures is the number among the first r days minus the number among the first l − 1. All the trees of “the first i days” are needed at once, and storing them as copies is too expensive.
3The idea
A persistent segment tree over values: version i is the tree of the first i days. A new version differs from the previous one by one day, that is, only by the path from the root to the leaf of its temperature: this path is copied, and the rest is shared. The descent looks for the k-th in two versions at once, r and l − 1: the left child has countr − countl−1 days of the period; if k is no larger, go left, otherwise subtract and go right.
4Walkthrough
Compress the temperatures into ranks in increasing order, so that the tree is over ranks rather than a range up to 109. Keep the nodes in three arrays, left child, right child, counter, and set up node 0, the empty tree, to which all empty branches refer: then version 0 is simply node 0. Each insertion adds ⌈log₂ V⌉ + 1 nodes, where V is the number of distinct temperatures. The arrays are best allocated at once for n·(⌈log₂ V⌉ + 1) + 1 nodes.
The Almaty archive has 505 distinct temperatures, and all 31,047 versions take 310 thousand nodes instead of 31 million as copies. The first question of the third test is the median of January 1941: −3.3°.
4+Solution
5Complexity
O(n log V) to build, O(log V) per question, O(n log V) memory.
6Common mistakes
- Version l instead of l − 1. The difference of versions r and l gives the days from the (l + 1)-th to the r-th: the first day of the period drops out. This is
wrong.py. - Changing old nodes. If on insertion the counter is corrected in a node of the previous version rather than in its copy, all old versions change too.
- Sorting each period. Correct, but 40,000 periods of ten thousand days each is hundreds of millions of operations.
Algorithms behind it
O(log n) per change and query
1 problem
DS
Data structure
Segment tree
The minimum, maximum and sum on any range with updates on the fly: both in O(log n).
O(log n) per query and per update
2 problems