CF2140D A Cruel Segment's Thesis

给你 $n$ 个在数轴上的线段，第 $i$ 条线段表示为 $[l_i, r_i]$。初始时，所有线段都是未标记的。 你将不断重复以下操作，直到没有未标记的线段为止： 1. 在第 $k$ 次操作中，如果目前有至少两条未标记的线段，任选两条未标记的线段 $[l_i, r_i]$ 和 $[l_j, r_j]$，将这两条线段都标记，并新增一条满足以下条件的标记线段 $[x_k, y_k]$： - $l_i \leq x_k \leq r_i$， - $l_j \leq y_k \leq r_j$， - $x_k \leq y_k$。 2. 如果只剩一条未标记的线段，则将其标记。 你的任务是求出执行完所有操作后，所有标记线段的长度之和的最大可能值。注意，线段 $([l, r])$ 的长度为 $r-l$。

每个测试点包含若干组测试数据。第一行为测试组数 $t$（$1 \le t \le 10^4$）。每组测试数据描述如下： 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示线段的数量。 接下来的 $n$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq 10^9$），表示第 $i$ 条线段。 保证所有测试组的 $n$ 之和不超过 $2 \times 10^5$。

对于每组测试数据，输出一个整数，表示能得到的所有标记线段长度之和的最大可能值。

在第一个示例中，我们选择这给定的两个线段，构造新线段 $[1, 10^9]$。 在第二个示例中，我们选择线段 $[1, 10]$ 和 $[2, 15]$，生成新线段 $[1,15]$。接着 $[3, 9]$ 是剩下的唯一未标记线段，下一个操作中将其标记。 由 ChatGPT 5 翻译