CF2140D.A Cruel Segment's Thesis

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

给你 $n$ 个在数轴上的线段，第 $i$ 条线段表示为 $[l_i, r_i]$ 。初始时，所有线段都是未标记的。

你将不断重复以下操作，直到没有未标记的线段为止：

在第 $k$ $k$ 次操作中，如果目前有至少两条未标记的线段，任选两条未标记的线段 $[l_i, r_i]$ $[l_{i}, r_{i}]$ 和 $[l_j, r_j]$ $[l_{j}, r_{j}]$ ，将这两条线段都标记，并新增一条满足以下条件的标记线段 $[x_k, y_k]$ $[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$ 。
如果只剩一条未标记的线段，则将其标记。

你的任务是求出执行完所有操作后，所有标记线段的长度之和的最大可能值。注意，线段 $([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

4
2
1 1000000000
1 1000000000
3
1 10
2 15
3 9
5
1 11
2 7
15 20
1 3
11 15
1
1000000000 1000000000

输出#1

在第一个示例中，我们选择这给定的两个线段，构造新线段 $[1, 10^9]$ 。

在第二个示例中，我们选择线段 $[1, 10]$ 和 $[2, 15]$ ，生成新线段 $[1,15]$ 。接着 $[3, 9]$ 是剩下的唯一未标记线段，下一个操作中将其标记。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?