#203EasyPrefix Sums & Difference Arrays· Difference Array for Range Updates

Booking Overlap Heatmap

A campsite is open for `days` days numbered `0` to `days - 1`. Each booking reserves a pitch for a range of consecutive days `[first, last]` (both inclusive). The manager wants a heatmap: for every day, how many bookings cover it. Return an array of length `days` whose value at index `d` is the number of bookings with `first <= d <= last`. Marking every day of every booking one by one is slow when bookings are long. Do the work in time proportional to `days` plus the number of bookings.

Input format

`days`: the number of days. `bookings`: a list of `[first, last]` pairs.

Output format

An array of `days` integers, the number of bookings covering each day.

Examples

Input: days = 5, bookings = [[0, 2], [1, 3], [2, 2]]

Output: [1, 2, 3, 1, 0]

Day 0 is covered once, day 1 twice, day 2 three times, day 3 once and day 4 never.

Input: days = 3, bookings = []

Output: [0, 0, 0]

With no bookings every day has a count of 0.

Constraints

1 <= days <= 10^5
0 <= bookings.length <= 10^5
0 <= first <= last < days

#difference-array
#prefix-sums
#arrays
#range-updates