#CF1000C. 覆盖点计数

覆盖点计数

CF1000C Covered Points Count

题目描述

\hspace{15pt}给定数轴上的 nn 条线段,每条线段的两个端点坐标都是整数。线段之间可以相交、嵌套或完全重合,也允许退化为一个点,即端点满足 li=ril_i = r_i。

\hspace{15pt}第 ii 条线段覆盖点 xx,当且仅当 li≦x≦ril_i \leqq x \leqq r_i。请对每个 k=1,2,…,nk = 1, 2, \dots, n,求出恰好被 kk 条线段覆盖的整数坐标点的数量。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n \left(1 \leqq n \leqq 2 \times 10^5\right) 代表线段数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $l_i, r_i \left(0 \leqq l_i \leqq r_i \leqq 10^{18}\right)$ 分别代表第 ii 条线段的左端点和右端点,该线段覆盖区间 [li,ri]\left[l_i, r_i\right] 内的全部整数点。

输出格式

\hspace{15pt}在一行上输出 nn 个整数 $\mathrm{cnt}_1, \mathrm{cnt}_2, \dots, \mathrm{cnt}_n$,相邻两个整数之间用一个空格隔开,其中 cntk\mathrm{cnt}_k 代表恰好被 kk 条线段覆盖的整数坐标点的数量。

测试样例

3
0 3
1 3
3 8
6 2 1

样例 1 解释

\hspace{15pt}三条线段分别为 [0,3]\left[0, 3\right]、[1,3]\left[1, 3\right] 和 [3,8]\left[3, 8\right]。

∙ \hspace{23pt}\bullet\,点 00 只被第 11 条线段覆盖,点 4,5,6,7,84, 5, 6, 7, 8 只被第 33 条线段覆盖,共 66 个点恰好被 11 条线段覆盖;

∙ \hspace{23pt}\bullet\,点 1,21, 2 同时被第 11 条和第 22 条线段覆盖,共 22 个点恰好被 22 条线段覆盖;

∙ \hspace{23pt}\bullet\,点 33 同时被三条线段覆盖,共 11 个点恰好被 33 条线段覆盖。

\hspace{15pt}因此依次输出 6,2,16, 2, 1。

3
1 3
2 4
5 7
5 2 0

样例 2 解释

\hspace{15pt}三条线段分别为 [1,3]\left[1, 3\right]、[2,4]\left[2, 4\right] 和 [5,7]\left[5, 7\right]。

∙ \hspace{23pt}\bullet\,恰好被 11 条线段覆盖的点为 1,4,5,6,71, 4, 5, 6, 7,共 55 个;

∙ \hspace{23pt}\bullet\,恰好被 22 条线段覆盖的点为 2,32, 3,共 22 个;

∙ \hspace{23pt}\bullet\,没有点被 33 条线段同时覆盖。

\hspace{15pt}因此依次输出 5,2,05, 2, 0。