← 返回题目列表

Codeforces · 1981/E

E. 海龟和相交的线段

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

Turtle 刚刚收到 $$$n$$$ 段和序列 $$$a_1, a_2, \ldots, a_n$$$。第$$$i$$$段是$$$[l_i, r_i]$$$。

Turtle 将创建一个无向图 $$$G$$$。如果线段 $$$i$$$ 和线段 $$$j$$$ 相交,则 Turtle 将为每个 $$$i \ne j$$$ 在 $$$i$$$ 和 $$$j$$$ 之间添加一条权重为 $$$|a_i - a_j|$$$ 的无向边。

Turtle 希望您计算图 $$$G$$$ 的最小生成树的边的权重之和,或者报告图 $$$G$$$ 没有生成树。

我们说两条线段 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 相交当且仅当 $$$\max(l_1, l_2) \le \min(r_1, r_2)$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

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

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$l_i, r_i, a_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$$$) — 第 $$$i$$$ 段和第 $$$i$$$序列的元素。

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

输出

对于每个测试用例,输出一个整数 - 图 $$$G$$$ 的最小生成树的边的权重之和。如果图$$$G$$$没有生成树,则输出$$$-1$$$。

示例

输入 #1

4
5
1 7 3
2 4 6
3 5 5
6 7 9
3 4 4
5
2 7 3
1 3 6
4 5 5
6 7 9
1 1 4
4
1 4 3
1 2 1
3 4 5
1 4 4
3
1 3 1
2 3 3
4 5 8

输出 #1

9
13
4
-1

注意

第一个测试用例中,图形$$$G$$$如下:

$$$G$$$的最小生成树之一如下:

最小生成树边的权重之和为$$$9$$$。

在第二个测试用例中,图形$$$G$$$如下:

$$$G$$$ 已经是一棵树,树的权重总和是 $$$13$$$。

在第三个测试用例中,图形$$$G$$$如下:

在第四个测试用例中,图形$$$G$$$如下:

很容易看出$$$G$$$没有连通,因此$$$G$$$没有生成树。