Conference
Contest: Codeforces Round 941 (Div. 1)
Difficulty rating: 3300
Tags: data structures, flows

You have been asked to organize a very important art conference. The first step is to choose the dates.

The conference must last for a certain number of consecutive days. Each day, one lecturer must perform, and the same lecturer cannot perform more than once.

You asked $$$n$$$ potential lecturers if they could participate in the conference. Lecturer $$$i$$$ indicated that they could perform on any day from $$$l_i$$$ to $$$r_i$$$ inclusive.

A certain segment of days can be chosen as the conference dates if there is a way to assign an available lecturer to each day of the segment, assigning each lecturer to no more than one day.

For each $$$k$$$ from $$$1$$$ to $$$n$$$, find how many ways there are to choose a segment of $$$k$$$ consecutive days as the conference dates.

Input format:
The first line of input contains one integer $$$n$$$ — the number of potential lecturers ($$$1 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ — the segment of available days for the $$$i$$$th lecturer ($$$1 \le l_i \le r_i \le 2 \cdot 10^5$$$).

Output format:
Print $$$n$$$ integers, where the $$$k$$$th number denotes the number of ways to select a segment of $$$k$$$ consecutive days as conference dates.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first testcase, a one-day conference can be organized on any of the days from $$$1$$$ to $$$6$$$. A two-day conference can be organized from day $$$2$$$ to day $$$3$$$, as well as from day $$$4$$$ to day $$$5$$$.

In the second testcase, five lecturers can perform only from day $$$1$$$ to day $$$3$$$, so it will not be possible to organize a conference longer than three days.

Example input:
3
1 2
3 4
5 6

Example output:
6
2
0

Example input:
5
1 3
1 3
1 3
1 3
1 3

Example output:
3
2
1
0
0

Editorial:
For a segment of days, how can we tell if there's a way to assign a lecturer to each day of the segment? Consider a bipartite graph: the first part consists of the days in the segment, the second part consists of all lecturers, an edge between a day and a lecturer exists if that lecturer is available on that day. We need to check if the maximum matching covers all vertices in the first part. If this is the case, we'll call the segment of days valid.
A common way to check if a segment is valid is to use Hall's marriage theorem. In our case, we can formulate it as follows:
• If for each subset of days $$$s$$$, the number of lecturers available on at least one day of that subset is at least $$$|s|$$$, then this segment of days is valid.
It might be tempting to only consider subsets which form contiguous subsegments. However, consider the following test case:
For a segment of days $$$[1; 3]$$$, the only subset that violates the Hall's marriage theorem condition is $$$\{1, 3\}$$$, which is not contiguous.
Let's try to fix that.
Suppose there are two lecturers with equal $$$l_i$$$: let their availability segments be $$$[a; b]$$$ and $$$[a; c]$$$, where $$$b \le c$$$. Then, if we replace $$$[a; c]$$$ with $$$[a+1; c]$$$, the answer does not change. This can be easily seen if you consider the set of all pairs of days that these two lecturers can cover, and notice that this set stays the same after the $$$[a; c] \rightarrow [a+1; c]$$$ transformation.
(Note that when $$$a = b = c$$$, replacing $$$[a; c]$$$ with $$$[a+1; c]$$$ is effectively equivalent to removing one of the lecturers: their segment becomes empty.)
We can keep applying this operation until all $$$l_i$$$ are distinct (potentially removing some lecturers in the process). This process can be simulated in $$$O(n \log n)$$$ time by going left to right using a priority queue.
Why is this transformation useful? Consider a subset of days $$$t$$$ that violates the Hall's marriage theorem condition. Suppose it's non-contiguous: say, days $$$x$$$ and $$$y$$$ ($$$x + 1 < y$$$) belong to $$$t$$$, while none of days $$$x+1, x+2, \ldots, y-1$$$ belong to $$$t$$$. Then, if we include days $$$x+1, x+2, \ldots, y-1$$$ into $$$t$$$, then $$$t$$$ will still violate the condition! (proof left as an exercise)
As a consequence, if we include all "gaps" in $$$t$$$, we'll still get a violating subset, but this time, it will be contiguous.
We have described a transformation that makes all $$$l_i$$$ distinct. Similarly, we can apply it in the same way to make all $$$r_i$$$ distinct. After that, we'll get another useful property: monotonicity. Specifically, if $$$t = [l; r]$$$ is a violating subset, then $$$[l-1; r]$$$ and $$$[l; r+1]$$$ are violating subsets as well.
Now we can see that a segment of days is valid iff it is not a violating subset itself (i.e. instead of checking all subsets of the segment, it's enough to just check the whole segment).
To finish the solution, we can use the two pointers technique to find all valid segments in linear time.
Bonus: solve the problem for $$$1 \le l_i \le r_i \le 10^{12}$$$.