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

「ROI 2025 Day2」最小化逆序对

题目背景

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

题目描述

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

你面前有一张 rrcc 列的表格 aa,里面填满了从 11rcr \cdot c 的所有不同数字,排列顺序完全随机。你的任务是将这些数字逐一转移到一个最初为空的数组 bb 中。

只要表格还没清空,你可以重复以下两种操作之一:

  • 操作 1:将表格第一行的元素按从左到右的顺序(从第一列到最后一列)添加到数组 bb 的末尾,然后删除表格的第一行。

  • 操作 2:将表格第一列的元素按从上到下的顺序(从第一行到最后一行)添加到数组 bb 的末尾,然后删除表格的第一列。

你需要巧妙选择操作的顺序,使得最终数组 bb 中的逆序对数量最少。逆序对是指数组中满足 1i<jrc1 \le i < j \le r \cdot cbi>bjb_i > b_j 的索引对 (i,j)(i, j)

输入格式

第一行包含两个整数 rrcc (rc,1rc2000000)(r \le c, 1 \le r \cdot c \le 2\,000\,000),分别表示表格的行数和列数。

接下来的 rr 行描述表格 aa。第 ii 行包含 cc 个整数 ai1,,aica_{i1}, \ldots, a_{ic} (1aijrc)(1 \le a_{ij} \le r \cdot c),表示表格第 ii 行的元素。

保证表格 aa 中的所有数字各不相同。

输出格式

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

2 3
3 4 1
5 6 2

6

2 3
2 3 4
1 6 5

2

提示

样例解释 1

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

样例解释 2

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


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

子任务 分值 附加限制
00 样例
11 1515 r+c14r + c \le 14
22 1818 rc500r \cdot c \le 500
33 55 所有行和列按升序排列,rc250000r \cdot c \le 250\,000
44 77 r=1r = 1rc250000r \cdot c \le 250\,000
55 66 r2r \le 2rc250000r \cdot c \le 250\,000
66 22 r20r \le 20rc250000r \cdot c \le 250\,000
77 1010 r,c100r, c \le 100
88 22 rc10000r \cdot c \le 10\,000
99 11 r100r \le 100c1000c \le 1000
1010 r100r \le 100c2500c \le 2500
1111 r100r \le 100c5000c \le 5000
1212 r100r \le 100c7500c \le 7500
1313 r100r \le 100c10000c \le 10\,000
1414 44 r100r \le 100c15000c \le 15\,000
1515 22 r100r \le 100c20000c \le 20\,000
1616 33 r,c200r, c \le 200
1717 r,c400r, c \le 400
1818 44 r,c600r, c \le 600
1919 11 r,c800r, c \le 800
2020 r,c1000r, c \le 1000
2121 r,c1200r, c \le 1200
2222 r,c1400r, c \le 1400
2323 rc100000r \cdot c \le 100\,000
2424 rc250000r \cdot c \le 250\,000
2525 44 rc500000r \cdot c \le 500\,000
2626 11 rc750000r \cdot c \le 750\,000
2727 rc1000000r \cdot c \le 1\,000\,000
2828 rc1500000r \cdot c \le 1\,500\,000
2929 无附加限制