CF1297I Falling Blocks

Polycarp 最近发明了一款新的手机游戏，游戏中有些方块从空中落下。 在游戏中，有 $ n $ 个方块依次落下，它们会掉到一个长度为 $ d $ 单位的平面上。每个方块可以看作一个矩形，范围从 $ l_i $ 到 $ r_i $，高度为 1 单位。方块从高空落下，直至接触到地面或其他方块。我们定义，如果 $ l_a \le l_b \le r_b \le r_a $ ，则称方块 $ a $ 覆盖方块 $ b $ 。 当一个新方块 $ i $ 下落时，如果它接触到的任一方块 $ j $，都没有被 $ i $ 覆盖，那么 $ i $ 就会粘在 $ j $ 上，而且没有方块会消失。否则，被 $ i $ 覆盖并与其接触的所有方块都会被蒸发掉，$ i $ 继续下落，直到接触到某个方块。 例如，假设三个方块按照顺序 $(1,2)$，$(2,3)$ 和 $(1,3)$ 下落。第一个方块会落到地面上。第二个方块会粘在第一个方块上。最后，第三个方块会蒸发第二个方块，然后继续下落蒸发第一个方块，最终落在地面上。 这里有一个图解说明第一个例子:  每当方块落下后，请帮助 Polycarp 计算剩下的方块数量。

第一行输入两个整数 $ n $ 和 $ d $ （$ 1 \le n, d \le 10^5 $），表示下落的方块个数和地面的长度。 接下来的 $ n $ 行，每行包含两个整数 $ l_i $ 和 $ r_i $ （$ 1 \le l_i \le r_i \le d $），表示第 $ i $ 个方块的左右坐标。

输出 $ n $ 个整数，第 $ i $ 个整数表示在第 $ i $ 个方块落下后，所剩的方块总数。

我们来看第二个例子的说明： - 第 1 个方块会直接落在地面上。 - 第 2 个方块也落在地面上。 - 第 3 个方块会粘在第 1 和第 2 个方块上。注意，第 3 个方块并不会蒸发第 2 个方块，因为它与第 1 个方块发生了接触但没有覆盖。 - 第 4 个方块则会蒸发掉所有方块，最后粘在地面上。 - 第 5 个方块会粘在第 4 个方块上。 - 第 6 个方块粘在第 5 个方块上。 - 第 7 个方块粘在第 6 个方块上，没有方块被蒸发，因为第 7 个方块虽然覆盖了第 4 和第 5 个方块，但没有与其接触。 - 第 8 个方块蒸发掉第 7 个方块，并粘在第 6 个方块上。 **本翻译由 AI 自动生成**