芝士典题。

解法

定义 $pre_i$ 表示 $a_i$ 上一次出现的位置。

不难发现，对于查询区间 $[l,r]$，如果 $\exists pre_x \ge l,x \in [l,r]$，则证明区间内存在相等的数。

考虑如何修改。

我们使用 set 维护每种数出现的位置。每个修改操作（$a_i \leftarrow x$）即为：在 $a_i$ 对应的 set 中删除 $i$，在 $x$ 对应的 set 中加入 $i$。$pre$ 值被影响的位置只有 $a_i$ 对应的 set 中 $i$ 的后继，$i$ 这个位置，$x$ 对应的 set 中 $i$ 的后继。更新后的 $pre$ 值即为这三个位置的前驱，可使用 lower_bound 函数求值。注意：要使用 set 内置的 lower_bound，否则复杂度是错误的。

注意特判边界！

维护一颗线段树，支持区间求 $\max$，单点修改即可。

不贴代码，自己找人要去。