P9653 『GROI-R2』 Non-Blank Canvas

As we all know, after Alice hid away, Tenniel sat in front of a blank canvas, picked up a piece of charcoal, and began to draw. But now the canvas is no longer blank, because the current scenery is already on it. Suppose the canvas length is $n$. The color at each unit position can be represented by a positive integer in the range $[1,k]$. Tenniel still wants to draw the teacup he has knocked over. Each time he draws, he may choose any position on the canvas and repaint the color at that position into any positive integer in $[1,k]$. In the end, we know this painting has memory. Define the number of memory fragments left on the painting as the **number of consecutive blocks of the same color**. Now Tenniel wants to know: given an **upper limit** on the number of times he can repaint, what is the **maximum** possible number of memory fragments on the painting? **Formal statement** You have $n$ consecutive cells. Each cell has an initial color $c_i$, and it is guaranteed that $1 \le c_i \le k$. You may perform **at most** $m$ operations. Each operation changes the color of one cell, and the new color must still be in $[1,k]$. We call a **maximal consecutive segment of the same color** one block. You need to find the **maximum** number of blocks after at most $m$ operations.

This problem has multiple test cases. The first line contains a positive integer $T$, denoting the number of test cases. For each test case, the first line contains three positive integers $n,m,k$, representing the canvas length, the upper limit of Tenniel’s painting operations, and the range of colors. The second line contains an integer sequence $c$ of length $n$, representing the initial color at each position on the canvas.

For each test case, output one positive integer per line, representing the maximum possible number of memory fragments.

**Sample explanation** For the first test case, Tenniel can repaint the second position from left to right to color $1$, obtaining $\{c_n\}=\{2,1,2\}$. The number of blocks is $3$. For the second test case, Tenniel can repaint the second position from left to right to color $1$, and repaint the third position from left to right to color $3$, obtaining $\{c_n\}=\{2,1,3,2,3\}$. The number of blocks is $5$. **Constraints** **This problem uses bundled testdata**. | $\text{Subtask}$ | $\sum n\le$ | $m\le$ | $k\le$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $10$ | $3$ | $10$ | | $2$ | $5\times 10^5$ | $1$ | $5\times 10^5$ | $10$ | | $3$ | $10^3$ | $10^3$ | $10^3$ | $15$ | | $4$ | $5\times 10^5$ | $5\times 10^5$ | $3$ | $25$ | | $5$ | $5\times 10^5$ | $5\times 10^5$ | $5\times 10^5$ | $40$ | For $100\%$ of the testdata, $1\le n\le 5\times 10^5$, $1\le \sum n\le 5\times 10^5$, $1\le m\le n$, $3\le k \le 5\times 10^5$, and $1\le c_i\le k$. Translated by ChatGPT 5