[AdditionalFile4891.zip](file://AdditionalFile4891.zip?type=additional_file)

#4891. 「ROI 2025 Day2」最小化逆序对

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

译自 ROI 2025 Day2 T3. Минимизация инверсий

你面前有一张 $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

输入

2 3
3 4 1
5 6 2

输出

6

在第一个样例中，最小逆序对数量可以通过两次删除第一行实现。最终数组 $b$ 为 $[3, 4, 1, 5, 6, 2]$，包含 $6$ 个逆序对。

样例 2

输入

2 3
2 3 4
1 6 5

输出

2

在第二个样例中，为了达到最小逆序对数量，可以先删除第一列，再两次删除第一行。最终数组 $b$ 为 $[2, 1, 3, 4, 6, 5]$，包含 $2$ 个逆序对。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。