A server writes a log line for every request, and the timestamps (in seconds) are stored in a list times in non-decreasing order; several requests can share a second. An on-call dashboard asks many questions of the form "how many requests arrived between second a and second b, inclusive?".
Write count_in_range(times: list[int], queries: list[list[int]]) -> list[int] that returns, for each query [a, b], the number of entries t in times with a <= t <= b.
times = [3, 5, 5, 5, 8, 12, 12, 20]
count_in_range(times, [[5, 5], [4, 12], [0, 2], [13, 19], [0, 100], [12, 20]])
# [3, 6, 0, 0, 8, 3]
0 <= len(times) <= 2 * 10^5;0 <= times[i] <= 10^9, sorted non-decreasing.0 <= len(queries) <= 2 * 10^5; each query has0 <= a <= b <= 10^9.- Counting by walking the list is O(n) per query, billions of steps at these sizes. Aim for O((n + q) log n).
- Don't use the
bisectmodule: write the search loop.
Show hint
the entries inside [a, b] form one contiguous stretch of times. Find where that stretch starts and where it ends, each with its own search.