CF2258D Magic Tiles

Magic Tiles 是一款全球知名的钢琴游戏，本题以此作为背景。Noyan 不擅长需要快速反应和高度集中注意力的游戏，因此他只能用一根手指，也就是说每一行最多只能按下一个音符。此外，如果他连续按下同一列的音符，他将根据连续按下的长度获得成比例的分数。但是，如果他按错了音符，他就会被淘汰。请帮助 Noyan 决定如何选择音符，使他的总分最大。 你将得到一个 $10^{18}$ 行、2 列的网格。行的编号为 $1$ 到 $10^{18}$，列的编号为 $1$ 和 $2$。每个格子要么是白色要么是黑色。 你需要选择一些黑色格子组成的子集，要求每一行最多选择一个格子。你的目标是最大化总得分 $S$，其中 $S$ 是分别对每一列计算得分后求和。 单列的得分定义为 $$ \sum_{i=1}^{k} 100^{100^{x_i}}, $$ 其中 $k$ 是该列被选择的最大连续段数，$x_i$ 是第 $i$ 个段的长度。 请你确定能够获得的最大总分。 由于网格非常大，输入以每一列最大黑色区间的压缩形式给出。你还需要按压缩格式输出答案。有关细节请参见输入输出格式部分。

每个测试点包含若干测试用例。第一行包含测试用例数 $t$（$1 \le t \le 3000$）。每个测试用例描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3000$）——分别表示第一列和第二列的黑色区间段数。 接下来的 $n$ 行描述第一列的黑色区间。第 $i$ 行包含两个整数 $l_{1, i}$ 和 $r_{1, i}$（$1 \le l_{1, i} \le r_{1, i} \le 10^{18}$），表示一个从第 $l_{1, i}$ 行到第 $r_{1, i}$ 行（包含两端）的连续黑色格子区间。 再接下来的 $m$ 行描述第二列的黑色区间。第 $j$ 行包含两个整数 $l_{2, j}$ 和 $r_{2, j}$（$1 \le l_{2, j} \le r_{2, j} \le 10^{18}$），表示从第 $l_{2, j}$ 行到第 $r_{2, j}$ 行（包含两端）的连续黑色格子区间。 同一列内，任何两个区间之间均不相邻，形式化地，对于所有合法 $i$，$r_{1,i}+1 < l_{1,i+1}$，$r_{2,j}+1 < l_{2,j+1}$。 保证所有测试用例中 $n$ 之和不超过 $3000$，$m$ 之和不超过 $3000$。

对于每个测试用例，输出两行。 第一行输出一个整数 $c$（$1\leq c$）——表示所有被选中的最大连续段的总数。 第二行输出 $c$ 个整数 $x_1, x_2, \ldots, x_c$，表示所有被选中段的长度，要求按非递增顺序排列（$x_1 \ge x_2 \ge \cdots \ge x_c \ge 1$）。

在第一个测试用例中，两段黑色区间没有重叠。我们在第一列选中第 $1$ 到第 $3$ 行，在第二列选中第 $5$ 到第 $6$ 行，最终得到两个区间，长度分别为 $3$ 和 $2$。 在第二个测试用例中，两列在第 $1$ 到第 $4$ 行都为黑色。由于每一行最多只能选一个格子，我们只能从其中一列把这 $4$ 个格子全选，于是只会有一个长度为 $4$ 的区间。 在第三个测试用例中，一种最优的选法为： - 在第一列选中第 $1$、$2$ 行； - 在第二列选中第 $3$ 到第 $7$ 行； - 在第一列选中第 $8$ 行； - 在第二列选中第 $9$ 到第 $12$ 行。 于是第一列的被选区间长度为 $2$ 和 $1$，第二列的为 $5$ 和 $4$，合起来按照非递增顺序排序的结果为 $[5,4,2,1]$。 可以证明，以上给出的方案在这些测试用例中均为最优方案。    上分别是第一、二、三组样例的方格图。红色表示被选中的格子。 由 ChatGPT 5 翻译