P9697 [GDCPC 2023] Canvas

有一个长度为 $n$ 的序列，一开始序列中的所有元素均为 $0$。另外还有 $m$ 个操作，其中第 $i$ 个操作会将序列中第 $l_i$ 个元素的值改为 $x_i$，以及将序列中第 $r_i$ 个元素的值改为 $y_i$。每个操作必须恰好执行一次。 求执行操作的最优顺序，使得所有操作执行完成后，序列中所有元素之和最大。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$2 \leq n, m \leq 5 \times 10^5$）表示序列的长度和操作的个数。 对于接下来 $m$ 行，第 $i$ 行输入四个整数 $l_i$，$x_i$，$r_i$ 和 $y_i$（$1 \leq l_i

每组数据首先输出一行一个整数，表示执行操作后，所有元素的最大和。接下来输出一行 $m$ 个由单个空格分隔的整数 $a_1, a_2, \cdots, a_m$ 表示执行操作的最优顺序，其中 $a_i$ 表示第 $i$ 次执行的操作的编号。从 $1$ 到 $m$ 的每个整数（含两端）必须恰好出现一次。若有多种合法答案，您可以输出任意一种。 **【样例解释】** 对于第一组样例数据，按 $4, 1, 3, 2$ 的顺序执行操作后，序列变为 $\{2, 2, 2, 1\}$，元素之和为 $7$。 对于第二组样例数据，按 $2, 1$ 的顺序执行操作后，序列变为 $\{2, 0, 2, 1\}$，元素之和为 $5$。

For the first sample test case, after performing operations $4, 1, 3, 2$ in order, the sequence becomes $\{2, 2, 2, 1\}$. The sum of all elements is $7$. For the second sample test case, after performing operations $2, 1$ in order, the sequence becomes $\{2, 0, 2, 1\}$. The sum of all elements is $5$.