In the recently conducted Goodbye 2024 contest, there was a problem(B) regarding intervals.

In the official solution and the submissions I saw, the fact that played a major role was that 1 <= l <= r <= 2*n.

This allowed us to make an array of size 2*n and then use prefix sums to find how many intervals of size 1 completely occupy some interval having size > 1.

What if the limit would have been 1e9 instead of 2*n?

For this modification, I was thinking, we can first store all the intervals of size 1 in a new array (let's say b). Then loop over b and merge intervals and at the end we will have some non-overlapping intervals. Now, taking these new intervals from array b, we need to find out how many intervals of size > 1 from the original array are completely contained in these newly built intervals from array b.

Is there a fast way to check this? In other words, we have two arrays a and b and we want to find out which intervals from a are completely contained in some interval from array b (where intervals in b are non-overlapping). Both a and b can be of the size of O(n) with 1 <= n <= 1e5. How can we solve this problem in atmost O(nlogn)?