CF1000C Covered Points Count
题目描述
给定数轴上的 n 条线段,每条线段的两个端点坐标都是整数。线段之间可以相交、嵌套或完全重合,也允许退化为一个点,即端点满足 li=ri。
第 i 条线段覆盖点 x,当且仅当 li≦x≦ri。请对每个 k=1,2,…,n,求出恰好被 k 条线段覆盖的整数坐标点的数量。
输入格式
第一行输入一个整数 n(1≦n≦2×105) 代表线段数量。
此后 n 行,第 i 行输入两个整数 $l_i, r_i \left(0 \leqq l_i \leqq r_i \leqq 10^{18}\right)$ 分别代表第 i 条线段的左端点和右端点,该线段覆盖区间 [li,ri] 内的全部整数点。
输出格式
在一行上输出 n 个整数 $\mathrm{cnt}_1, \mathrm{cnt}_2, \dots, \mathrm{cnt}_n$,相邻两个整数之间用一个空格隔开,其中 cntk 代表恰好被 k 条线段覆盖的整数坐标点的数量。
测试样例
3
0 3
1 3
3 8
6 2 1
样例 1 解释
三条线段分别为 [0,3]、[1,3] 和 [3,8]。
∙点 0 只被第 1 条线段覆盖,点 4,5,6,7,8 只被第 3 条线段覆盖,共 6 个点恰好被 1 条线段覆盖;
∙点 1,2 同时被第 1 条和第 2 条线段覆盖,共 2 个点恰好被 2 条线段覆盖;
∙点 3 同时被三条线段覆盖,共 1 个点恰好被 3 条线段覆盖。
因此依次输出 6,2,1。
3
1 3
2 4
5 7
5 2 0
样例 2 解释
三条线段分别为 [1,3]、[2,4] 和 [5,7]。
∙恰好被 1 条线段覆盖的点为 1,4,5,6,7,共 5 个;
∙恰好被 2 条线段覆盖的点为 2,3,共 2 个;
∙没有点被 3 条线段同时覆盖。
因此依次输出 5,2,0。