题解

思路

设查询区间长度为 $k$。若区间内所有数互不相同，那么它们能重排成连续整数，当且仅当区间最大值减最小值等于 $k-1$。因此关键是同时维护区间最大值、最小值和“是否出现重复”。

做法

小规模做法

每次查询复制区间并排序。排序后依次检查相邻元素之差是否都为一。修改直接写回原数组。该做法单次查询为 $O(k\log k)$，适用于 $n,m\le 500$。

无修改做法

定义 $pre_i$ 为位置 $i$ 左侧最近的、与 $a_i$ 相等的位置；若不存在则为零。区间 $[l,r]$ 内没有重复，当且仅当区间内所有 $pre_i<l$。

序列不修改时，可以预处理每个位置的 $pre_i$，再分别建立区间最小值、最大值和 $pre$ 最大值的稀疏表。每次查询为 $O(1)$，预处理为 $O(n\log n)$。

小值域做法

当所有值不超过 $256$ 时，在线段树的每个结点保存该区间出现值的 bitset，并记录合并过程中是否发现重复。左右儿子的 bitset 有交集就说明存在重复。查询得到 bitset、重复标记、最小值和最大值后即可判定。单次修改和查询均为 $O(\frac{256}{64}\log n)$。

满分做法

动态维护每种数值出现位置的有序集合，同时维护每个位置的 $pre_i$。一次单点修改只会改变：被删除位置、旧值集合中它的后继、新值集合中它的后继，这些位置的 $pre$。

在线段树中维护区间最小值、最大值和 $pre$ 最大值。查询 $[l,r]$ 时，若 max(pre) < l 且 max(a)-min(a)=r-l，答案为 damushen，否则为 yuanxing。

每次集合前驱/后继查找、线段树修改和查询都是 $O(\log n)$，总复杂度为 $O((n+m)\log n)$，空间复杂度为 $O(n)$。

正确性说明

对任意位置 $i\in[l,r]$，若 $pre_i\ge l$，则 $a_i$ 在区间中至少出现两次；反之，区间中若有重复值，取该值在区间内第二次出现的位置，其前驱一定仍在区间内。因此 max(pre)<l 与区间元素互异等价。

在元素互异的前提下，长度为 $k$ 的整数集合至少覆盖 $k$ 个不同整数。其最大值与最小值之差等于 $k-1$ 时，闭区间内恰有 $k$ 个整数，集合只能恰好包含它们全部；反之连续整数显然满足该式。两项条件合取即为题目要求。

复杂度

小规模做法单次查询为 $O(k\log k)$；无修改做法预处理 $O(n\log n)$、单次查询 $O(1)$；小值域做法单次操作为 $O(\frac{256}{64}\log n)$；满分做法总时间为 $O((n+m)\log n)$，空间为 $O(n)$。