比赛链接

给定一个长度为 $n$ 的序列 $\{a\}$，每次操作可以任取一个位置并将该位置的数移到序列末尾。

问最少需要多少次操作才能使序列中所有大小相同的数相邻。

显然只需要在序列中选定一些位置，然后按特定顺序将他们移除就可以完成任务。定义 $\text{dp}(i)$ 表示不选择序列 $[i,n]$ 中的位置个数的最大值。

维护每个值 $v$ 的最靠左出现的位置 $l_v$，最靠右出现的位置 $r_v$，动态维护 $[i,n]$ 中出现的次数 $c_v$。

如果保留位置 $i$ 。当 $i=l_{a_i}$ 时，需要移除 $[i,r_{a_i}]$ 中所有不等于 $a_i$ 的位置，即 $\text{dp}(i)\gets c_{a_i}+\text{dp}(r_{a_i}+1)$。

当 $i\neq l_{a_i}$ 时，若不保留 $l_{a_i}$ 的位置，则 $l_{a_i}$ 的位置的数会被加到位置 $n$ 后面。

为了使得 $l_{a_i}$ 的位置的数与 $i$ 位置的数所在段相邻，需要移除 $[i,n]$ 中所有不等于 $a_i$ 的位置，于是 $\text{dp}(i)\gets c_{a_i}$。

若保留 $l_{a_i}$ 的位置，则该情况会在计算 $\text{dp}(l_{a_i})$ 时考虑，此时不考虑。

如果不保留位置 $i$，则 $\text{dp}(i)\gets \text{dp}(i+1)$。