P12507 「ROI 2025 Day2」最小化逆序对

由于评测机性能差异，本题时限增加了 3 秒。

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day2 T3.** ***[Минимизация инверсий](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day2.pdf)*** 你面前有一张 $r$ 行 $c$ 列的表格 $a$，里面填满了从 $1$ 到 $r \cdot c$ 的所有不同数字，排列顺序完全随机。你的任务是将这些数字逐一转移到一个最初为空的数组 $b$ 中。 只要表格还没清空，你可以重复以下两种操作之一： - **操作 1**：将表格第一行的元素按从左到右的顺序（从第一列到最后一列）添加到数组 $b$ 的末尾，然后删除表格的第一行。  - **操作 2**：将表格第一列的元素按从上到下的顺序（从第一行到最后一行）添加到数组 $b$ 的末尾，然后删除表格的第一列。  你需要巧妙选择操作的顺序，使得最终数组 $b$ 中的逆序对数量最少。逆序对是指数组中满足 $1 \le i < j \le r \cdot c$ 且 $b_i > b_j$ 的索引对 $(i, j)$。

第一行包含两个整数 $r$ 和 $c$ $(r \le c, 1 \le r \cdot c \le 2\,000\,000)$，分别表示表格的行数和列数。 接下来的 $r$ 行描述表格 $a$。第 $i$ 行包含 $c$ 个整数 $a_{i1}, \ldots, a_{ic}$ $(1 \le a_{ij} \le r \cdot c)$，表示表格第 $i$ 行的元素。 保证表格 $a$ 中的所有数字各不相同。

输出一个整数，表示通过所有操作后，数组 $b$ 中可能的最小逆序对数量。

### 样例解释 1 在第一个样例中，最小逆序对数量可以通过两次删除第一行实现。最终数组 $b$ 为 $[3, 4, 1, 5, 6, 2]$，包含 $6$ 个逆序对。 ### 样例解释 2 在第二个样例中，为了达到最小逆序对数量，可以先删除第一列，再两次删除第一行。最终数组 $b$ 为 $[2, 1, 3, 4, 6, 5]$，包含 $2$ 个逆序对。 --- 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | |$0$|$0$|样例|| | $1$ | $15$ | $r + c \le 14$ | $0$ | | $2$ | $18$ | $r \cdot c \le 500$ | $0,1$ | | $3$ | $5$ | 所有行和列按升序排列，$r \cdot c \le 250\,000$ | | | $4$ | $7$ | $r = 1$，$r \cdot c \le 250\,000$ | | | $5$ | $6$ | $r \le 2$，$r \cdot c \le 250\,000$ | $4$ | | $6$ | $2$ | $r \le 20$，$r \cdot c \le 250\,000$ | $0,1,4,5$ | | $7$ | $10$ | $r, c \le 100$ | $0,1$ | | $8$ | $2$ | $r \cdot c \le 10\,000$ | $0,1,2,7$ | | $9$ | $1$ | $r \le 100$，$c \le 1000$ | $0,1,2,7$ | | $10$ | $1$ | $r \le 100$，$c \le 2500$ | $0,1,2,7,9$ | | $11$ | $1$ | $r \le 100$，$c \le 5000$ | $0,1,2,7,9,10$ | | $12$ | $1$ | $r \le 100$，$c \le 7500$ | $0,1,2,7,9-11$ | | $13$ | $1$ | $r \le 100$，$c \le 10\,000$ | $0,1,2,7-12$ | | $14$ | $4$ | $r \le 100$，$c \le 15\,000$ | $0,1,2,7-13$ | | $15$ | $2$ | $r \le 100$，$c \le 20\,000$ | $0,1,2,7-14$ | | $16$ | $3$ | $r, c \le 200$ | $0, 1, 7$ | | $17$ | $3$ | $r, c \le 400$ | $0, 1, 7, 16$ | | $18$ | $4$ | $r, c \le 600$ | $0, 1, 2, 7, 16, 17$ | | $19$ | $1$ | $r, c \le 800$ | $0, 1, 2, 7, 16-18$ | | $20$ | $1$ | $r, c \le 1000$ | $0, 1, 2, 7, 9, 16-19$ | | $21$ | $1$ | $r, c \le 1200$ | $0, 1, 2, 7, 9, 16-20$ | | $22$ | $1$ | $r, c \le 1400$ | $0, 1, 2, 7, 9, 16-21$ | | $23$ | $1$ | $r \cdot c \le 100\,000$ | $0, 1, 2, 7-9, 16$ | | $24$ | $1$ | $r \cdot c \le 250\,000$ | $0, 1-10, 16, 17, 23$ | | $25$ | $4$ | $r \cdot c \le 500\,000$ | $0,1-11,16-18,23,24$ | | $26$ | $1$ | $r \cdot c \le 750\,000$ | $0,1-12,16-19,23-25$ | | $27$ | $1$ | $r \cdot c \le 1\,000\,000$ | $0,1-13,16-20,23-26$ | | $28$ | $1$ | $r \cdot c \le 1\,500\,000$ | $0,1-14,16-21,23-27$ | | $29$ | $1$ | 无附加限制 | $0,1-28$ |