P16545 [EGOI 2026] 狐狸家族 / Fox Families

最近，阿尔卑斯山脉（Alps）的一大片区域被划定为自然保护区。 起初，保护区内并没有狐狸。然而，多亏了持续的保护措施，保护区内的狐狸种群数量逐日恢复。每天都有一只新的狐狸到来。 生物学家 Simona 正在观察这恢复过程，她对狐狸在任何时间点形成的独特家族数量很感兴趣。Simona 知道每只狐狸 $i$ 都有一个狩猎领地，可以用线段 $[L_i, R_i]$ 表示，其中 $L_i < R_i$。这些领地可能会重叠，甚至相互包含。 根据她的研究，Simona 知道如果两只狐狸 $i$ 和 $j$ 的狩猎领地中，有一个领地嵌套在另一个领地内（即 $L_i \leq L_j < R_j \leq R_i$ 或 $L_j \leq L_i < R_i \leq R_j$），那么它们就是**直接亲属**关系。 两只狐狸属于同一个**家族**，当且仅当它们要么是直接亲属，要么通过一系列直接亲属的狐狸链相连。正式地说，两只狐狸 $a$ 和 $b$ 属于同一个家族，当且仅当存在一个狐狸序列 $c_0, c_1, \dots c_{m-1}$，使得 $a = c_0$ 且 $b = c_{m-1}$，并且对于每个 $0 \leq i < m-1$，$c_i$ 与 $c_{i+1}$ 是直属关系。 狐狸 $i$ ($0 \leq i \leq N-1$) 在第 $i$ 天到达，并从那时起一直留在保护区内，永久保持相同的狩猎领地 $[L_i, R_i]$。每只狐狸的到来可能会也可能不会改变家族关系。每天过后，Simona 都想知道狐狸 $i$ 到达后，现存的狐狸家族数量。

输入的第一行包含一个整数 $N$，表示天数。接下来的 $N$ 行，每行包含两个整数 $L_i$ 和 $R_i$，描述狐狸 $i$ 的狩猎领地。

输出 $N$ 行。第 $i$ 行（对于 $0 \leq i \leq N-1$）应包含一个整数，表示狐狸 $i$ 到达后存在的狐狸家族数量。

### 样例解释 第一个样例满足子任务 1、2 和 5 的限制。第二个样例满足子任务 1、2、3 和 5 的限制。第三个样例满足子任务 1、2、4 和 5 的限制。 **第一个样例。** 第一只狐狸到达后，有一个家族。第二只狐狸到达后，有两个家族，因为 $[1, 4]$ 和 $[3, 6]$ 重叠但没有任何一个领地包含另一个。然后，领地为 $[3, 4]$ 的狐狸到达：它被 $[1, 4]$ 和 $[3, 6]$ 包含，所以这两个家族合并，家族数量现在为 $1$。最后，领地为 $[6, 7]$ 的狐狸没有包含任何之前的领地，也没有被包含在它们之中，因此它形成了一个新的家族，家族数量现在为 $2$。 :::align{center}  ::: ### 约束条件 - $1 \leq N \leq 100\ 000$. - $0 \leq L_i < R_i \leq 200\ 000$. - 对于任意两个领地，$(L_i, R_i)$ 不会重复出现。 ### 评分方式 你的程序将在分成若干子任务的测试数据上进行测试。要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。 - **子任务 $0$** [$0$ 分]: 样例。 - **子任务 $1$** [$10$ 分]: $N \le 100$。 - **子任务 $2$** [$15$ 分]: $N \le 2000$。 - **子任务 $3$** [$16$ 分]: $R_i - L_i \le 2$。 - **子任务 $4$** [$23$ 分]: $L_i < L_{i+1}$。 - **子任务 $5$** [$36$ 分]: 没有额外的约束条件。