CF1566D2 Seating Arrangements (hard version)

这是该问题的困难版本。唯一的区别在于本版本中 $1 \le n \le 300$。 在电影院中，座位可以表示为一个有 $n$ 行 $m$ 列的表格。行编号为 $1$ 到 $n$。每一行的座位从左到右依次编号：第 $k$ 行的座位编号为 $m(k-1)+1$ 到 $mk$，对于所有 $1 \le k \le n$ 的行。 $$ \begin{aligned} &1 \\ &2\quad \cdots\quad m-1\quad m\quad m+1 \\ &m+2\quad \cdots\quad 2m-1\quad 2m\quad 2m+1 \\ &2m+2\quad \cdots\quad 3m-1\quad 3m\quad \vdots \\ &\vdots\quad \ddots\quad \vdots\quad \vdots\quad m(n-1)+1 \\ &m(n-1)+2\quad \cdots\quad nm-1\quad nm \end{aligned} $$ 上表为座位编号表。 有 $nm$ 个人想去电影院看一部新电影。他们编号为 $1$ 到 $nm$。你需要为每个人分配一个且仅一个座位。 已知在这个电影院中，座位编号越小，观看效果越好。第 $i$ 个人的视力水平为 $a_i$。记 $s_i$ 为分配给第 $i$ 个人的座位编号。你希望视力水平较低的人能获得更好的座位，因此对于任意两个人 $i$ 和 $j$，如果 $a_i < a_j$，则应满足 $s_i < s_j$。 所有人分配好座位后，他们会依次入场并入座。从 $1$ 到 $nm$，每个人依次进入影厅并坐到自己的座位上。每个人会先到达自己所在的行，然后从该行的第一个座位开始，向右移动到自己的座位。在移动过程中，有些座位是空的，有些已被前面的人占据。某个人的不便度等于他经过的已被占用的座位数。 举个例子：$m=5$，某人被分配到第一行的第 $4$ 号座位，第一行的 $1$、$3$、$5$ 号座位已被占用，$2$ 和 $4$ 号座位是空的。这个人的不便度为 $2$，因为他经过了已被占用的 $1$ 和 $3$ 号座位。 请你计算，在满足所有条件的情况下，最小化所有人的不便度之和。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300$），分别表示行数和每行的座位数。 每个测试用例的第二行包含 $n \cdot m$ 个整数 $a_1, a_2, \ldots, a_{n \cdot m}$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示第 $i$ 个人的视力水平。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示可以获得的最小总不便度。

在第一个测试用例中，只有一种分配座位的方式：第一个人坐在第一个座位，第二个人坐在第二个座位。总不便度为 $1$。 在第二个测试用例中，最优的座位分配如下图所示：  在第三个测试用例中，最优的座位分配如下图所示：  每个格子中的数字表示坐在该座位上的人的编号。 由 ChatGPT 4.1 翻译