CF1650C Weight of the System of Nested Segments

在数轴上有 $m$ 个点，第 $i$ 个点的整数坐标为 $x_i$，权值为 $w_i$。所有点的坐标均不相同，点的编号为 $1$ 到 $m$。 一组长度为 $n$ 的区间序列 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ 被称为“嵌套区间系统”，如果对于每一对 $i, j$（$1 \le i < j \le n$），都有 $l_i < l_j < r_j < r_i$。换句话说，第 $2$ 个区间严格嵌套在第 $1$ 个区间内，第 $3$ 个区间严格嵌套在第 $2$ 个区间内，依此类推。 给定一个正整数 $n$，请你构造一个嵌套区间系统，要求： - 每个区间的两个端点都必须是给定的 $m$ 个点之一； - 所有区间端点所用点的权值之和 $2 \cdot n$ 最小。 例如，设 $m = 8$。下图中给出了所有点，红色为权值，蓝色为坐标。构造一个包含三个嵌套区间的系统： - 第一个区间的权值：$1 + 1 = 2$ - 第二个区间的权值：$10 + (-1) = 9$ - 第三个区间的权值：$3 + (-2) = 1$ - 系统所有区间权值之和：$2 + 9 + 1 = 12$  三层嵌套区间系统

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例前有一个空行。 每个测试用例的第一行为两个正整数 $n$（$1 \le n \le 10^5$）和 $m$（$2n \le m \le 2 \cdot 10^5$）。 接下来的 $m$ 行，每行包含两个整数 $x_i$（$-10^9 \le x_i \le 10^9$）和 $w_i$（$-10^4 \le w_i \le 10^4$），分别表示第 $i$ 个点的坐标和权值（$1 \le i \le m$）。所有 $x_i$ 互不相同。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n+1$ 行：第一行输出所构造系统的最小权值和，接下来的 $n$ 行，每行输出两个整数，表示第 $i$ 个区间的两个端点的编号（$1 \le i \le n$）。每个区间的两个端点输出顺序不限——可以先输出左端点编号，也可以先输出右端点编号。 如果存在多种权值和最小的嵌套区间系统，输出任意一种均可。

第一个测试用例与题目描述中的示例一致。可以证明该系统的权值和最小。 第二个测试用例只有 $6$ 个点，因此你需要用所有点来构造 $3$ 个区间。 由 ChatGPT 4.1 翻译