← 返回题目列表

Codeforces · 1741/F

F. 多色段

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

Dmitry 在坐标轴 $$$Ox$$$ 上有 $$$n$$$ 个不同颜色的段。每个段由三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$c_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$) 表征,其中 $$$l_i$$$ 和 $$$r_i$$$ 是第 $$$i$$$ 段末端的坐标,并且$$$c_i$$$ 是它的颜色。

Dmitry 喜欢寻找线段之间的最小距离。然而,他认为成对的相同颜色的片段无趣。因此,他想知道每个线段从该线段到最近的不同颜色线段的距离。

两个线段之间的距离是第一个线段的点和第二个线段的点之间的距离的最小值。特别是,如果线段相交,则它们之间的距离等于 $$$0$$$。

例如,Dmitry 有 $$$5$$$ 段:

- 第一条线段与第二条线段相交(这些是不同颜色的线段),因此它们的答案等于 $$$0$$$。
- 对于 $$$3$$$-rd 段,最近的不同颜色的段是 $$$2$$$-nd 段,其距离等于 $$$2$$$。
- 对于第 $$$4$$$ 段,最近的不同颜色的段是第 $$$5$$$ 段,其距离等于 $$$1$$$。
- 第 $$$5$$$ 段位于第 $$$2$$$ 段内(这些是不同颜色的段),因此它们的答案等于 $$$0$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行描述包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 段数。

接下来的 $$$n$$$ 行包含段的描述。每个段由三个整数 $$$l_i$$$、$$$r_i$$$ 和 $$$c_i$$$ 描述 ($$$1 \le l_i \le r_i \le 10^9, 1 \le c_i \le n$$$) — 第 $$$i$$$ 段左端和右端的坐标,以及该段的颜色。保证至少有 $$$2$$$ 不同颜色的段。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行上打印 $$$n$$$ 整数,其中第 $$$i$$$ 数字等于从第 $$$i$$$ 段到最近的不同颜色段的距离。

示例

输入 #1

9
3
1 2 1
3 4 1
5 6 2
2
100000000 200000000 1
900000000 1000000000 2
5
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
5
1 5 1
4 9 2
1 2 1
8 9 2
5 7 3
2
1 100 2
10 90 1
3
1 1 1
10 10 2
1000000000 1000000000 3
3
3 4 1
2 5 1
1 6 2
6
5 6 2
11 12 3
7 8 2
3 4 2
1 2 1
9 10 2
2
1 3 1
2 3 2

输出 #1

3 1 1 
700000000 700000000 
0 0 0 0 0 
0 0 2 1 0 
0 0 
9 9 999999990 
0 0 0 
3 1 3 1 1 1 
0 0

输入 #2

4
8
11 16 7
12 15 7
2 5 8
17 22 5
1 8 8
19 23 8
16 16 6
6 7 5
9
1 4 3
5 11 1
8 11 3
1 10 1
2 11 1
1 10 4
3 11 1
5 7 1
1 11 1
9
25 25 1
26 26 1
24 24 2
13 14 2
12 16 2
17 18 1
19 19 1
24 27 2
24 27 1
9
15 18 1
20 22 2
13 22 2
13 22 2
3 13 2
6 10 2
3 6 2
19 24 2
22 24 2

输出 #2

0 1 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 3 1 1 3 0 0 
0 2 0 0 2 5 9 1 4

注意

在第一个样本的第一个测试用例中,只有一个颜色段为$$$2$$$,所有其他段的颜色为$$$1$$$。因此,对于颜色 $$$1$$$ 的线段,答案等于到 $$$3$$$rd 线段的距离,而对于 $$$3$$$rd 线段,答案等于到 $$$1$$$ 颜色线段的距离的最小值。

在第一个样本的第二个测试用例中,只有 $$$2$$$ 段,对于它们来说,答案等于它们之间的距离。

在第一个示例的第三个测试用例中,每个线段至少其一端与不同颜色的线段相交,因此所有答案都等于 $$$0$$$。

第一个样本的第四个测试用例在问题陈述中进行了描述。

在第一个样本的第五个测试用例中,一个段完全位于另一个段内,对于它们来说,答案都是 $$$0$$$。

在第一个样本的第六个测试用例中,所有线段都是不同颜色的点。