P11134 【MX-X5-T6】「GFOI Round 1」Abiogenesis
题目背景
原题链接：。
---
> [Abiogenesis - Juggernaut.](https://music.163.com/#/song?id=1416321652)
本题为 [Codeforces 1981 E. Turtle and Intersected Segments](https://codeforces.com/contest/1981/problem/E) 改编。
题目描述
给 $n$ 条线段 $[l_i, r_i]$，第 $i$ 条线段有一组权值 $a_i, b_i$。
有一个无向图 $G$，其初始有 $n$ 个结点，$0$ 条边。对于每一对正整数 $i, j$ 满足 $1 \le i < j \le n$，若编号为 $i, j$ 的线段相交，就在 $G$ 中连一条两个端点分别为 $i, j$，边权为 $a_i + a_j + |b_i - b_j|$ 的边。
求 $G$ 最小生成树边权之和，或报告 $G$ 不连通。
如果两条线段 $[l_1, r_1]$ 和 $[l_2, r_2]$ 满足 $\max(l_1, l_2) \le \min(r_1, r_2)$，就认为它们是相交的。
输入格式
无
输出格式
无
说明/提示
**【样例解释】**
对于第一组数据，$G$ 的形态如下：
$G$ 的其中一个最小生成树形态如下：
**【数据范围】**
**本题采用捆绑测试且开启子任务依赖。**
| 子任务编号 | $n \le$ | $\sum n \le$ | 特殊性质 | 子任务依赖 | 分值 |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $1$ | $100$ | $10^5$ | 无 | 无 | $11$ |
| $2$ | $10^5$ | $10^5$ | AC | 无 | $5$ |
| $3$ | $10^5$ | $10^5$ | A | $2$ | $14$ |
| $4$ | $10^5$ | $10^5$ | B | 无 | $14$ |
| $5$ | $10^5$ | $10^5$ | C | $2$ | $14$ |
| $6$ | $10^5$ | $10^5$ | D | 无 | $14$ |
| $7$ | $10^5$ | $10^5$ | 无 | $1, 2, 3, 4, 5, 6$ | $28$ |
- 特殊性质 A：$\forall i \in [1, n], l_i = 1$。
- 特殊性质 B：$\forall i \in [1, n - 1], l_i \le l_{i + 1}, r_i \le r_{i + 1}$。
- 特殊性质 C：$\forall i \in [1, n], b_i = 1$。
- 特殊性质 D：$\forall i \in [1, n], a_i = b_i$。
对于所有数据，满足 $1 \le T \le 10^4$，$1 \le n, \sum n \le 10^5$，$1 \le l_i, r_i, a_i, b_i \le 10^8$，$l_i \le r_i$。