题解

思路

操作要求目标颜色在被替换区间内完全不存在，因此一次操作既可以把若干不同颜色合并成一种新颜色，也可以消去某种已有颜色。直接只记录区间最终颜色不足以描述“先消去某颜色，再整体染色”的过程，因此需要两个互补状态。

设 $F(l,r,c)$ 表示把区间 $[l,r]$ 全部变成颜色 $c$ 的最少操作数。区间两端已经等于 $c$ 的元素无需处理，可以先删去这些端点。

设 $G(l,r,c)$ 表示让区间 $[l,r]$ 中不再出现颜色 $c$ 的最少操作数。此时两端本来就不等于 $c$ 的元素同样可以先删去。

做法

对于 $F(l,r,c)$，有两类转移：

1. 先用 $G(l,r,c)$ 消去区间中的颜色 $c$，再用一次操作把整个区间染成 $c$；
2. 枚举分界点，把左右两个区间分别变成 $c$。

对于 $G(l,r,c)$，也有两类转移：

1. 枚举分界点，分别消去左右区间中的颜色 $c$；
2. 枚举另一种颜色 $d\ne c$，把整个区间变成 $d$，这样区间中自然不再含有 $c$。

所有状态使用记忆化搜索。最终答案是所有颜色 $c$ 对应的 $F(1,n,c)$ 的最小值。

子任务 1 可以把整个数组状态作为搜索结点，枚举所有合法区间和目标颜色进行 BFS。

当 $x\le2$ 时，数组可压缩成若干极长同色段。每次最优操作可以把一个内部同色段改成相邻颜色，使连续段数量减少 $2$；边界操作至多减少 $1$。因此若连续段数为 $s$，答案为 $\lfloor s/2\rfloor$，可以在线性时间内求出。

正确性证明

经过端点裁剪后，$F(l,r,c)$ 的最优方案最后一步要么把一个已经不含 $c$ 的完整区间染成 $c$，对应 $G(l,r,c)+1$；要么不存在覆盖整个区间的最后一步，此时最优操作序列可以在某个分界点拆成左右两部分，分别由两个 $F$ 状态完成。两类情况覆盖全部可能。

同理，经过裁剪后，$G(l,r,c)$ 的最优方案要么可以按某个分界点拆开，分别消去两侧的 $c$；要么存在一步把覆盖当前区间的部分统一成另一颜色 $d\ne c$，这由 $F(l,r,d)$ 完整描述。因此 $G$ 的转移也无遗漏。

状态只转移到裁剪后更小的区间、区间划分或互补目标，记忆化搜索会得到每个状态的最优值。对最终颜色取最小值，得到全数组变为任意同色数组的最少操作数。

复杂度

状态数为 $O(n^2x)$。每个状态枚举分界点或颜色，总时间复杂度为 $O(n^3x+n^2x^2)$，在 $x\le n$ 时为 $O(n^4)$；空间复杂度为 $O(n^2x)$。