CF1870C Colorful Table

给定两个整数 $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$，输出包含所有该颜色格子的最小矩形的宽度与高度之和。

在第一个测试用例中，整个数组 $b$ 都是颜色 $1$，因此颜色 $1$ 的最小矩形大小为 $2 \times 2$，两边之和为 $4$。 在第二个测试用例中，数组 $b$ 如下所示： 1112 其中一个角落的格子是颜色 $2$，其余三个格子是颜色 $1$。因此颜色 $1$ 的最小矩形大小为 $2 \times 2$，颜色 $2$ 的最小矩形大小为 $1 \times 1$。 在最后一个测试用例中，数组 $b$ 如下所示： 1111112221123211222111111 由 ChatGPT 4.1 翻译