← 返回题目列表

Codeforces · 1000/C

C. 覆盖点数

中文机器翻译题面 查看原题

坐标线上有 $$$n$$$ 段;每个线段的每个端点都有整数坐标。有些段可以退化为点。线段可以相互交叉、相互嵌套甚至重合。

您的任务如下:对于 [1..n]$$$ 中的每个 $$$k \,计算具有整数坐标的点的数量,使得覆盖这些点的线段数量等于 $$$k$$$。当且仅当 $$$l_i \le x \le r_i$$$ 时,具有端点 $$$l_i$$$ 和 $$$r_i$$$ 的线段覆盖点 $$$x$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 段数。

接下来的 $$$n$$$ 行包含段。第 $$$i$$$ 行包含一对整数 $$$l_i, r_i$$$ ($$$0 \le l_i \le r_i \le 10^{18}$$$) — 第 $$$i$$$ 段的端点。

输出

打印 $$$n$$$ 空格分隔的整数 $$$cnt_1, cnt_2, \dots, cnt_n$$$,其中 $$$cnt_i$$$ 等于点的数量,使得覆盖这些点的线段数量等于 $$$i$$$。

示例

输入 #1

3
0 3
1 3
3 8

输出 #1

6 2 1

输入 #2

3
1 3
2 4
5 7

输出 #2

5 2 0

注意

描述第一个示例的图片:

坐标为 $$$[0, 4, 5, 6, 7, 8]$$$ 的点被一段覆盖,点 $$$[1, 2]$$$ 被两段覆盖,点 $$$[3]$$$ 被三段覆盖。

描述第二个示例的图片:

点 $$$[1, 4, 5, 6, 7]$$$ 被一段覆盖,点 $$$[2, 3]$$$ 被两段覆盖,没有点被三段覆盖。