310686: CF1870C. Colorful Table
Description
You are given two integers $n$ and $k$. You are also given an array of integers $a_1, a_2, \ldots, a_n$ of size $n$. It is known that for all $1 \leq i \leq n$, $1 \leq a_i \leq k$.
Define a two-dimensional array $b$ of size $n \times n$ as follows: $b_{i, j} = \min(a_i, a_j)$. Represent array $b$ as a square, where the upper left cell is $b_{1, 1}$, rows are numbered from top to bottom from $1$ to $n$, and columns are numbered from left to right from $1$ to $n$. Let the color of a cell be the number written in it (for a cell with coordinates $(i, j)$, this is $b_{i, j}$).
For each color from $1$ to $k$, find the smallest rectangle in the array $b$ containing all cells of this color. Output the sum of width and height of this rectangle.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follows the description of the test cases.
The first line of each test case contains two integers $n$ and $k$ ($1 \leq n, k \leq 10^5$) — the size of array $a$ and the number of colors.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq k$) — the array $a$.
It is guaranteed that the sum of the values of $n$ and $k$ over all test cases does not exceed $10^5$.
OutputFor each test case, output $k$ numbers: the sums of width and height of the smallest rectangle containing all cells of a color, for each color from $1$ to $k$.
ExampleInput5 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 1Output
4 4 2 0 6 6 2 0 8 6 10 6 2Note
In the first test case, the entire array $b$ consists of color $1$, so the smallest rectangle for color $1$ has a size of $2 \times 2$, and the sum of its sides is $4$.
In the second test case, the array $b$ looks like this:
| 1 | 1 |
| 1 | 2 |
One of the corner cells has color $2$, and the other three cells have color $1$. Therefore, the smallest rectangle for color $1$ has a size of $2 \times 2$, and for color $2$ it is $1 \times 1$.
In the last test case, the array $b$ looks like this:
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 1 |
| 1 | 2 | 3 | 2 | 1 |
| 1 | 2 | 2 | 2 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Output
给定两个整数n和k，以及一个大小为n的整数数组a1, a2, …, an，其中对于所有1 ≤ i ≤ n，有1 ≤ ai ≤ k。定义一个大小为n×n的二维数组b，其中bi,j = min(ai, aj)。将数组b表示为一个方阵，其中左上角的单元格是b1,1，行从上到下编号为1到n，列从左到右编号为1到n。一个单元格的颜色是写在其上的数字（对于坐标为(i, j)的单元格，这是bi,j）。
对于从1到k的每个颜色，找到数组b中包含该颜色所有单元格的最小矩形。输出这个矩形的宽度和高度之和。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。然后是测试用例的描述。
- 每个测试用例的第一行包含两个整数n和k（1 ≤ n, k ≤ 10^5），分别表示数组a的大小和颜色的数量。
- 每个测试用例的第二行包含n个整数a1, a2, …, an（1 ≤ ai ≤ k），表示数组a。
- 保证所有测试用例的n和k的值之和不超过10^5。
输出：
- 对于每个测试用例，输出k个数字：对于从1到k的每个颜色，包含该颜色所有单元格的最小矩形的宽度和高度之和。
示例输入输出：
输入：
```
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
```
输出：
```
4
4 2
0 6 6 2 0
8 6
10 6 2
```
注意：
- 在第一个测试用例中，整个数组b只包含颜色1，所以颜色1的最小矩形大小为2×2，其边长之和为4。
- 在第二个测试用例中，数组b如下所示：
```
1 1
1 2
```
其中一个角单元颜色为2，其余三个单元颜色为1。因此，颜色1的最小矩形大小为2×2，颜色2的最小矩形大小为1×1。
- 在最后一个测试用例中，数组b如下所示：
```
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
```
对于颜色1，最小矩形大小为5×5，对于颜色2，最小矩形大小为3×3，对于颜色3，最小矩形大小为1×1。因此，输出分别为10、6和2。题目大意： 给定两个整数n和k，以及一个大小为n的整数数组a1, a2, …, an，其中对于所有1 ≤ i ≤ n，有1 ≤ ai ≤ k。定义一个大小为n×n的二维数组b，其中bi,j = min(ai, aj)。将数组b表示为一个方阵，其中左上角的单元格是b1,1，行从上到下编号为1到n，列从左到右编号为1到n。一个单元格的颜色是写在其上的数字（对于坐标为(i, j)的单元格，这是bi,j）。 对于从1到k的每个颜色，找到数组b中包含该颜色所有单元格的最小矩形。输出这个矩形的宽度和高度之和。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。然后是测试用例的描述。 - 每个测试用例的第一行包含两个整数n和k（1 ≤ n, k ≤ 10^5），分别表示数组a的大小和颜色的数量。 - 每个测试用例的第二行包含n个整数a1, a2, …, an（1 ≤ ai ≤ k），表示数组a。 - 保证所有测试用例的n和k的值之和不超过10^5。 输出： - 对于每个测试用例，输出k个数字：对于从1到k的每个颜色，包含该颜色所有单元格的最小矩形的宽度和高度之和。 示例输入输出： 输入： ``` 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 ``` 输出： ``` 4 4 2 0 6 6 2 0 8 6 10 6 2 ``` 注意： - 在第一个测试用例中，整个数组b只包含颜色1，所以颜色1的最小矩形大小为2×2，其边长之和为4。 - 在第二个测试用例中，数组b如下所示： ``` 1 1 1 2 ``` 其中一个角单元颜色为2，其余三个单元颜色为1。因此，颜色1的最小矩形大小为2×2，颜色2的最小矩形大小为1×1。 - 在最后一个测试用例中，数组b如下所示： ``` 1 1 1 1 1 1 2 2 2 1 1 2 3 2 1 1 2 2 2 1 1 1 1 1 1 ``` 对于颜色1，最小矩形大小为5×5，对于颜色2，最小矩形大小为3×3，对于颜色3，最小矩形大小为1×1。因此，输出分别为10、6和2。