Home => ProblemSet => [CF1741F]Multi-Colored Segments
2299: [CF1741F]Multi-Colored Segments
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
Dmitry 在坐标轴 Ox 上有 n 条不同颜色的线段。每条线段由三个整数 li、ri 和 ci 描述（1≤li≤ri≤109,1≤ci≤n），其中 li 和 ri 分别表示第 i 条线段的两个端点的坐标，ci 表示该线段的颜色。
Dmitry 喜欢寻找线段之间的最小距离。但他认为同色线段之间的配对没有意思。因此，他想知道对于每一条线段，到最近的不同颜色的线段的距离是多少。
两条线段之间的距离定义为：第一条线段上的某个点与第二条线段上的某个点之间距离的最小值。特别地，如果两条线段相交，则它们之间的距离为 0。
例如，Dmitry 有 5 条线段：
Dmitry 喜欢寻找线段之间的最小距离。但他认为同色线段之间的配对没有意思。因此，他想知道对于每一条线段，到最近的不同颜色的线段的距离是多少。
两条线段之间的距离定义为：第一条线段上的某个点与第二条线段上的某个点之间距离的最小值。特别地，如果两条线段相交，则它们之间的距离为 0。
例如，Dmitry 有 5 条线段：
- 第一条线段与第二条线段相交（且颜色不同），所以它们的答案都是 0。
- 对于第 3 条线段，最近的不同颜色线段是第 2 条，与其的距离为 2。
- 对于第 4 条线段，最近的不同颜色线段是第 5 条，与其的距离为 1。
- 第 5 条线段完全位于第 2 条线段内部（且颜色不同），所以它们的答案都是 0。
Input
输入的第一行包含一个整数 t（1≤t≤104），表示测试用例的数量。
接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 n（2≤n≤2*105），表示线段的数量。
接下来的 n 行，每行包含三个整数 li、ri 和 ci（1≤li≤ri≤109,1≤ci≤n），分别表示第 i 条线段的左端点、右端点和颜色。保证至少有 2 条线段颜色不同。
保证所有测试用例中 n 的总和不超过 2*105。
接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 n（2≤n≤2*105），表示线段的数量。
接下来的 n 行，每行包含三个整数 li、ri 和 ci（1≤li≤ri≤109,1≤ci≤n），分别表示第 i 条线段的左端点、右端点和颜色。保证至少有 2 条线段颜色不同。
保证所有测试用例中 n 的总和不超过 2*105。
Output
对于每个测试用例，输出一行 n 个整数，第 i 个数表示第 i 条线段到最近的不同颜色线段的距离。
Sample Input Copy
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
Sample Output Copy
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
HINT
样例二：
输入：
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
输出：
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 条线段的距离；对于第 3 条线段，答案等于到颜色为 1 的线段的最小距离。
在第一个样例的第二个测试用例中，只有 2 条线段，对于它们来说，答案等于它们之间的距离。
在第一个样例的第三个测试用例中，每条线段的至少一个端点与不同颜色的线段相交，所以所有答案都是 0。
第一个样例的第四个测试用例在题目描述中已经给出。
在第一个样例的第五个测试用例中，一条线段完全包含在另一条线段内部，对于它们来说，答案都是 0。
在第一个样例的第六个测试用例中，所有线段都是不同颜色的点。
输入：
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
输出：
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 条线段的距离；对于第 3 条线段，答案等于到颜色为 1 的线段的最小距离。
在第一个样例的第二个测试用例中，只有 2 条线段，对于它们来说，答案等于它们之间的距离。
在第一个样例的第三个测试用例中，每条线段的至少一个端点与不同颜色的线段相交，所以所有答案都是 0。
第一个样例的第四个测试用例在题目描述中已经给出。
在第一个样例的第五个测试用例中，一条线段完全包含在另一条线段内部，对于它们来说，答案都是 0。
在第一个样例的第六个测试用例中，所有线段都是不同颜色的点。