P15348 [TOIP 2025] Monochrome Stairs and Two-Color Stairs

In an $m \times n$ grid, each cell has exactly one color, and we use uppercase English letters to represent each color. A “stair” means: several consecutive vertical segments, where the bottom positions of these segments (the columns they are in) must be the same, and the height increases by $1$ step by step from left to right. Note that the height and width of a stair shape must be equal. A “monochrome stair” means: all cells covered by the stair have the same color. A “two-color stair” means: the cells covered by the stair contain exactly two colors. In the example figure below, the blue, yellow, and green shapes are “monochrome stairs” with width (height) $2$, $3$, and $4$, respectively. Note that stairs may overlap. For example, next to the blue $C$ stair there is another $C$ stair. Also, any large stair must contain smaller stairs. For example, in the figure below, the width $3$ $B$ stair contains $3$ stairs of width $2$. The width $4$ $A$ stair contains $3$ stairs of width $3$ and $6$ stairs of width $2$. :::align{center}  ::: In the following example figure, all “two-color stairs” are marked. :::align{center}  ::: Your task is to compute, for each possible width (height), how many monochrome stairs or two-color stairs there are.

$$ \begin{aligned} &m \; n \\ &a_{1,1} a_{1,2} a_{1,3} \cdots a_{1,n} \\ &a_{2,1} a_{2,2} a_{2,3} \cdots a_{2,n} \\ &a_{3,1} a_{3,2} a_{3,3} \cdots a_{3,n} \\ &\vdots \\ &a_{m,1} a_{m,2} a_{m,3} \cdots a_{m,n} \\ &q \end{aligned} $$ * $m$ and $n$ represent the height and width of the region, respectively. * $a_{i,j}$ represents the color of the region. * If $q=1$, query the number of monochrome stairs. If $q=2$, query the number of two-color stairs.

$$ \begin{aligned} &k \\ &s_1 \; s_2 \; s_3 \; \cdots \; s_k \end{aligned} $$ * $k$ is a non-negative integer, representing the maximum width (height) among all monochrome stairs (two-color stairs). * Each $s_i$ is a non-negative integer, representing the number of monochrome stairs (two-color stairs) with width (height) $i$. * If $k = 0$, output an empty line on the second line.

### Constraints * $1 \le m \le 4000$. * $1 \le n \le 4000$. * $a_{i,j}$ are uppercase English letters. * $m$ and $n$ are integers. * $q \in \{1,2\}$. ### Scoring This problem has five subtasks, with the constraints as follows. Each subtask may contain one or more testdata, and you will receive the score for that subtask only if all testdata in the subtask are answered correctly. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 5 | $q=1$, all $a_{i,j}$ are the same. | | 2 | 9 | $q=1$, $m \le 200$, $n \le 200$. | | 3 | 22 | $q=1$, $m \le 200$. | | 4 | 33 | $q=1$. | | 5 | 31 | $q=2$. | Translated by ChatGPT 5