分数: 300 点
问题陈述
有 N 二维平面上的城市。的坐标 i第城市是 (x_i, y_i)。这里 (x_1, x_2, \dots, x_N) 和 (y_1, y_2, \dots, y_N) 都是排列 (1, 2, \dots, N).
对于每个 k = 1,2,\dots,N,找到以下问题的答案:
Rng 在城市 k。 Rng 可以任意多次执行以下移动:
- 搬到另一个拥有较小规模的城市 x- 坐标和更小的 y- 坐标,或更大 x- 坐标和更大的 y- 坐标,比他当前所在的城市。
有多少个城市(包括市 k) 可从城市到达 k?
约束
- 1 \leq N \leq 200,000
- (x_1, x_2, \dots, x_N) 是一个排列 (1, 2, \dots, N).
- (y_1, y_2, \dots, y_N) 是一个排列 (1, 2, \dots, N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 x_2 y_2 : x_N y_N
输出
打印 N 行。在 i- 第行打印问题的答案 k = i.
示例输入 1
4 1 4 2 3 3 1 4 2
示例输出 1
1 1 2 2
Rng可以到达City 4 来自城市 3,或相反城市 3 来自城市 4.
示例输入 2
7 6 4 4 3 3 5 7 1 2 7 5 2 1 6
示例输出 2
3 3 1 1 2 3 2