P16545 [EGOI 2026] Fox Families

Recently, a large area of the Alps has been designated as a nature reserve. At first, there were no foxes in the reserve. However, thanks to continuous protection measures, the fox population in the reserve has been recovering day by day. Every day, one new fox arrives. Biologist Simona is observing this recovery process, and she is very interested in the number of distinct families formed by the foxes at any point in time. Simona knows that each fox $i$ has a hunting territory, which can be represented by a segment $[L_i, R_i]$, where $L_i < R_i$. These territories may overlap and may even contain one another. According to her research, Simona knows that if, for two foxes $i$ and $j$, one of their hunting territories is nested inside the other (that is, $L_i \leq L_j < R_j \leq R_i$ or $L_j \leq L_i < R_i \leq R_j$), then they are **direct relatives**. Two foxes belong to the same **family** if and only if they are either direct relatives, or they are connected by a chain of foxes where each adjacent pair are direct relatives. Formally, two foxes $a$ and $b$ belong to the same family if and only if there exists a sequence of foxes $c_0, c_1, \dots c_{m-1}$ such that $a = c_0$ and $b = c_{m-1}$, and for every $0 \leq i < m-1$, $c_i$ and $c_{i+1}$ are direct relatives. Fox $i$ ($0 \leq i \leq N-1$) arrives on day $i$ and stays in the reserve from then on, permanently keeping the same hunting territory $[L_i, R_i]$. The arrival of each fox may or may not change the family relations. After each day, Simona wants to know the number of fox families that exist after fox $i$ arrives.

The first line of input contains an integer $N$, the number of days. The next $N$ lines each contain two integers $L_i$ and $R_i$, describing the hunting territory of fox $i$.

Output $N$ lines. Line $i$ (for $0 \leq i \leq N-1$) should contain an integer, the number of fox families that exist after fox $i$ arrives.

### Sample Explanation The first sample satisfies the constraints of subtasks 1, 2, and 5. The second sample satisfies the constraints of subtasks 1, 2, 3, and 5. The third sample satisfies the constraints of subtasks 1, 2, 4, and 5. **First sample.** After the first fox arrives, there is one family. After the second fox arrives, there are two families, because $[1, 4]$ and $[3, 6]$ overlap but neither territory contains the other. Then, the fox with territory $[3, 4]$ arrives: it is contained in both $[1, 4]$ and $[3, 6]$, so these two families merge, and the number of families is now $1$. Finally, the fox with territory $[6, 7]$ neither contains any previous territory nor is contained in them, so it forms a new family, and the number of families is now $2$. :::align{center}  ::: ### Constraints - $1 \leq N \leq 100\ 000$. - $0 \leq L_i < R_i \leq 200\ 000$. - For any two territories, $(L_i, R_i)$ will not be repeated. ### Scoring Your program will be tested on testdata divided into several subtasks. To get the score for a subtask, you must solve all the testdata in that subtask correctly. - **Subtask $0$** [$0$ points]: Samples. - **Subtask $1$** [$10$ points]: $N \le 100$. - **Subtask $2$** [$15$ points]: $N \le 2000$. - **Subtask $3$** [$16$ points]: $R_i - L_i \le 2$. - **Subtask $4$** [$23$ points]: $L_i < L_{i+1}$. - **Subtask $5$** [$36$ points]: No additional constraints. Translated by ChatGPT 5