#P18635. Interval Problem

Interval Problem

Interval Problem

给定 nn 个区间 [li,ri][l_i,r_i]。将每个区间视为一个顶点;若两个区间相交,就在对应顶点之间连一条无向、无权边。

令 d(i,j)d(i,j) 表示第 ii 个区间对应的顶点到第 jj 个区间对应的顶点的最短路长度。如果两点之间不存在路径,定义 d(i,j)=0d(i,j)=0。自身到自身的距离也为0。

对于 i=1,2,…,ni=1,2,\ldots,n,分别计算

∑j=1nd(i,j).\sum_{j=1}^{n}d(i,j).

输入格式

第一行一个整数 nn。

随后 nn 行,第 ii 行两个整数 li,ril_i,r_i。

输出格式

输出 nn 行,第 ii 行表示原输入中第 ii 个区间的距离和。

数据范围

1≤n≤2×1051\le n\le2\times10^5,1≤li<ri≤2n1\le l_i<r_i\le2n。保证所有区间的全部 2n2n 个端点互不相同。

样例输入 1

5
2 3
6 7
1 9
5 10
4 8

样例输出 1

7
5
4
5
5