Turtle and Intersected Segments
Contest: Codeforces Round 949 (Div. 2)
Difficulty rating: 2600
Tags: data structures, dsu, graphs, greedy

Turtle just received $$$n$$$ segments and a sequence $$$a_1, a_2, \ldots, a_n$$$. The $$$i$$$-th segment is $$$[l_i, r_i]$$$.

Turtle will create an undirected graph $$$G$$$. If segment $$$i$$$ and segment $$$j$$$ intersect, then Turtle will add an undirected edge between $$$i$$$ and $$$j$$$ with a weight of $$$|a_i - a_j|$$$, for every $$$i \ne j$$$.

Turtle wants you to calculate the sum of the weights of the edges of the minimum spanning tree of the graph $$$G$$$, or report that the graph $$$G$$$ has no spanning tree.

We say two segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ intersect if and only if $$$\max(l_1, l_2) \le \min(r_1, r_2)$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the number of segments.

The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$l_i, r_i, a_i$$$ ($$$1 \le l_i \le r_i \le 10^9, 1 \le a_i \le 10^9$$$) — the $$$i$$$-th segment and the $$$i$$$-th element of the sequence.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the sum of the weights of the edges of the minimum spanning tree of the graph $$$G$$$. If the graph $$$G$$$ has no spanning tree, output $$$-1$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
In the first test case, the graph $$$G$$$ is as follows:

One of the minimum spanning trees of $$$G$$$ is as follows:

The sum of the weights of the edges of the minimum spanning tree is $$$9$$$.

In the second test case, the graph $$$G$$$ is as follows:

$$$G$$$ is already a tree, and the sum of the weights of the tree is $$$13$$$.

In the third test case, the graph $$$G$$$ is as follows:

In the fourth test case, the graph $$$G$$$ is as follows:

It's easy to see that $$$G$$$ is not connected, so $$$G$$$ has no spanning tree.

Example input:
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

Example output:
9
13
4
-1

Editorial:
We observe that for three segments $$$(l_1, r_1, a_1), (l_2, r_2, a_2), (l_3, r_3, a_3)$$$ where each pair of segments intersects (assume $$$a_1 \le a_2 \le a_3$$$), we only need to keep the edges between $$$(1, 2)$$$ and $$$(2, 3)$$$, because $$$a_3 - a_1 = a_2 - a_1 + a_3 - a_2$$$ and for every cycle in a graph, the edge with the maximum weight will not appear in the minimum spanning tree.
Therefore, consider the following scanline process: each segment is added at $$$l$$$ and removed at $$$r$$$. When adding a segment, find its predecessor and successor in the order sorted by $$$a$$$ and connect edges accordingly. Essentially, we maintain all the segments that exist at each moment as a chain sorted by $$$a$$$.
It is easy to see that after the scanline process, the number of edges is reduced to $$$O(n)$$$. Then we can directly compute the minimum spanning tree.
Time complexity: $$$O(n \log n)$$$ per test case.