Warm days
A weather archive stores the mean temperature for each of n days, in tenths of a degree. Two kinds of requests come to the archive, intermixed:
1 l r x: how many days from day l to day r were no colder than x, that is, had a temperature of at least x;2 l r d: a correction: it turned out that from day l to day r the sensor was off, and d must be added to all these days.
Answer all requests of the first kind. Four tests are the real archive: the mean temperature of Almaty for each day of 1941–2025 from the ERA5 reanalysis. In one of them, for each summer, the question is how many days from June to August were warmer than +25°.
In the example, at first three days out of six are no colder than 3.5°: 4.0, 5.0 and 6.0. After a correction of +1.0° for days two to four there are four of them, and day three is now exactly 4.0°.
Input
The first line holds n and q (1 ≤ n ≤ 50,000, 1 ≤ q ≤ 5000). The second holds n integer temperatures. Then q lines of four integers: the type, l, r (1 ≤ l ≤ r ≤ n) and x or d. All numbers, and all temperatures after corrections, are at most 109 in absolute value.
Output
The answers to the requests of the first kind, one per line, in the order of the requests.
Examples
Example 1
6 4 10 20 30 40 50 60 1 1 6 35 2 2 4 10 1 1 6 35 1 3 3 40
3 4 1
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
Reading all the days of a period is up to 50,000 steps per request, and there are thousands of requests. Whole chunks need to answer at once. What do you need to know about a chunk to count the days in it no colder than x quickly?
2Hint 2
If a chunk’s values are sorted, the answer is a binary search. And a correction to the whole chunk does not change the order: it need not be written into each value but can be remembered for the chunk as a whole.
3The idea
Square-root decomposition: cut the days into blocks of B ≈ √n. A block has a sorted copy of its values and a common addend. A period [l, r] covers several blocks whole and cuts at most two. A whole block answers by binary search: it has as many days no colder than x as there are values in the copy at least x − addend. In the cut blocks we look at the days one by one. A correction to a whole block is one addition to the addend; to a cut one, correct its days and re-sort the copy.
4Walkthrough
A segment tree does not help here: “how many values are at least x” cannot be assembled from the answers of halves unless a node stores a sorted list, and a correction to a whole range destroys such lists. Blocks are simpler: nothing inside a block needs gluing, and an addend to a whole block leaves the list untouched.
A request costs O(B + (n/B) log B): up to 2B days one by one and a binary search for each of the n/B blocks. A correction costs O(B log B + n/B). At B = √n on fifty thousand days that is up to 450 days one by one and about 220 binary searches per request instead of 50,000 steps.
On the Almaty archive the answers to the summer questions show warming: in 1941–1950 there were on average 20 days warmer than +25° per summer, in 2016–2025, 33, and in the summer of 2025, 53.
4+Solution
5Complexity
O((n + q·√n) log n) time and O(n) memory.
6Common mistakes
- Forgetting to re-sort. After a correction to part of a block its days have changed, but the sorted copy has not. While the block is cut by queries the error is invisible; as soon as it is asked as a whole, the binary search runs over the old values. That is
wrong.py. - Forgetting the addend in a cut block. A day in a cut block is its value plus the block’s addend: corrections to the whole block may have come earlier.
- Sorting the copy with the addend. If the addend is written into the copy, the next correction to the whole block has to be written into all the values again, and the gain is lost.