← 返回题目列表

Codeforces · 1566/D2

D2. 座位安排(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是在这个版本中 $$$1 \le n \le 300$$$。

在电影院中,座位可以表示为具有 $$$n$$$ 行和 $$$m$$$ 列的表格。这些行用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。每行中的座位从左到右用连续整数编号:在第 $$$k$$$ 行中,所有行从 $$$m (k - 1) + 1$$$ 到 $$$m k$$$ 为 $$$1 \le k \le n$$$。

$$$1$$$$$$2$$$$$$\cdots$$$$$$m - 1$$$$$$m$$$$$$m + 1$$$$$$m + 2$$$$$$\cdots$$$$$$2 m - 1$$$$$$2 m$$$$$$2m + 1$$$$$$2m + 2$$$$$$\cdots$$$$$$3 m - 1$$$$$$3 m$$$$$$\vdots$$$$$$\vdots$$$$$$\ddots$$$$$$\vdots$$$$$$\vdots$$$$$$m (n - 1) + 1$$$$$$m (n - 1) + 2$$$$$$\cdots$$$$$$n m - 1$$$$$$n m$$$ 带有座位索引的桌子

有$$$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

7
1 2
1 2
3 2
1 1 2 2 3 3
3 3
3 4 4 1 1 1 1 1 2
2 2
1 1 2 1
4 2
50 50 50 50 3 50 50 50
4 2
6 6 6 6 2 2 9 6
2 9
1 3 3 3 3 3 1 1 3 1 3 1 1 3 3 1 1 3

输出 #1

1
0
4
0
0
0
1

注意

在第一个测试用例中,有一种分配座位的方式:第一个人坐在第一个位置,第二个人坐在第二个位置。总的不便是$$$1$$$。

在第二个测试用例中,最佳座位如下所示:

在第三个测试用例中,最佳座位如下所示:

单元格中的数字是坐在该位置的人的索引。