题解

思路推导

把“不含任何只出现一次的数”的子段称为坏子段。若选定若干位置，并把这些位置分别改成互不相同且未在原数组出现过的整数，则所有包含选定位置的子段都会含有一个只出现一次的新整数。因此问题等价于：选择最少的位置，使每个坏子段至少包含一个被选位置。

坏子段都是区间。区间最小命中问题可以按右端点从小到大贪心：遇到第一个尚未被命中的坏子段时，选择它的右端点。任何可行方案都必须在这个区间内选择一个位置，而把该位置换到最右端不会削弱它对后续区间的覆盖能力。

于是从左到右扫描右端点 $r$，维护上一次选择位置后的起点 $s$。若存在某个 $l\in[s,r]$ 使 $[l,r]$ 是坏子段，就把 $r$ 选为新的修改位置，并令 $s=r+1$。

做法

对固定的右端点 $r$，令 $f(l)$ 表示子段 $[l,r]$ 中恰好出现一次的不同整数个数。存在坏子段当且仅当区间 $l\in[s,r]$ 上的最小 $f(l)$ 等于 $0$。

设新加入的数 $x=a_r$ 此前最近三次出现位置依次为 $p_1,p_2,p_3$，不存在的位置视为 $-1$。加入 $x$ 后：

• 当 $l\in(p_1,r]$ 时，$x$ 从未出现变为出现一次，$f(l)$ 增加 $1$；
• 当 $l\in(p_2,p_1]$ 时，$x$ 从出现一次变为出现两次，$f(l)$ 减少 $1$；
• 更早的左端点中，$x$ 加入前后都不只出现一次，$f(l)$ 不变。

用支持区间加和区间最小值的线段树维护所有左端点的 $f(l)$。每加入一个元素，只需做两次区间加，再查询 $[s,r]$ 的最小值。若最小值为零，就执行一次贪心选择。

正确性证明

把选中位置替换为两两不同的新整数后，任何包含至少一个选中位置的子段都会含有只出现一次的新整数；不包含选中位置的子段保持不变。因此合法修改集合恰好是所有原坏子段的命中集合。

按右端点顺序考虑第一个尚未命中的坏子段 $[l,r]$。任意合法方案必须在 $[l,r]$ 内选一点。把该点替换为 $r$ 后，所有右端点不小于 $r$、且原本被该点命中的后续区间仍会被 $r$ 命中，所以选择 $r$ 不劣。由交换论证，逐次选择当前坏子段右端点得到最少选择数。

线段树维护的 $f(l)$ 恰为 $[l,r]$ 中只出现一次的数的个数：每个新元素只会在其最近两次出现位置划出的两个左端点区间上改变“出现一次”的状态，区间更新与上述变化完全一致。因此查询最小值为零当且仅当当前存在尚未命中的坏子段，算法执行的选择序列正是最优区间命中贪心，答案正确。

复杂度分析

每个元素进行常数次线段树区间操作。单个测试用例的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。