← 返回题目列表

Codeforces · 1870/C

C. 彩色桌子

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

给你两个整数 $$$n$$$ 和 $$$k$$$。您还会获得一个大小为 $$$n$$$ 的整数数组 $$$a_1, a_2, \ldots, a_n$$$。已知对于所有$$$1 \leq i \leq n$$$,$$$1 \leq a_i \leq k$$$。

定义一个大小为 $$$n \times n$$$ 的二维数组 $$$b$$$,如下所示:$$$b_{i, j} = \min(a_i, a_j)$$$。将数组 $$$b$$$ 表示为正方形,其中左上角单元格为 $$$b_{1, 1}$$$,行从上到下从 $$$1$$$ 到 $$$n$$$ 编号,列从左到右从 $$$1$$$ 到 $$$n$$$ 编号。令单元格的颜色为其中写入的数字(对于坐标为 $$$(i, j)$$$ 的单元格,这是 $$$b_{i, j}$$$)。

对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色,在数组 $$$b$$$ 中找到包含该颜色所有单元格的最小矩形。输出该矩形的宽度和高度之和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n, k \leq 10^5$$$) — 数组 $$$a$$$ 的大小和颜色数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$) — 数组 $$$a$$$。

保证所有测试用例的$$$n$$$和$$$k$$$的值之和不超过$$$10^5$$$。

输出

对于每个测试用例,输出 $$$k$$$ 数字:包含颜色所有单元格的最小矩形的宽度和高度之和,对于从 $$$1$$$ 到 $$$k$$$ 的每种颜色。

示例

输入 #1

5
2 1
1 1
2 2
1 2
3 5
3 2 4
4 2
1 2 1 2
5 3
1 2 3 2 1

输出 #1

4 
4 2 
0 6 6 2 0 
8 6 
10 6 2

注意

在第一个测试用例中,整个数组 $$$b$$$ 由颜色 $$$1$$$ 组成,因此颜色 $$$1$$$ 的最小矩形的大小为 $$$2 \times 2$$$,其边长之和为 $$$4$$$。

在第二个测试用例中,数组 $$$b$$$ 如下所示:

1112

角单元格之一的颜色为 $$$2$$$,其他三个单元格的颜色为 $$$1$$$。因此,颜色 $$$1$$$ 的最小矩形的大小为 $$$2 \times 2$$$,颜色 $$$2$$$ 的最小矩形大小为 $$$1 \times 1$$$。

在最后一个测试用例中,数组 $$$b$$$ 如下所示:

1111112221123211222111111