题目分析

本题要求处理多个区间查询，每个查询需返回区间 [l, r] 内不同贝壳（元素）的个数。数据范围为 n ≤ 50000，m ≤ 200000，若采用暴力遍历每个区间的方法（时间复杂度 $O(m \times n)$），会因时间超限无法通过，因此需要更高效的算法。

算法标签

离线处理、

树状数组（Fenwick Tree）、

排序优化

算法原理

我们采用离线处理 + 树状数组的方法，核心思路是通过记录元素上一次出现的位置，结合树状数组快速统计区间内的不同元素个数。

1. 记录元素的历史位置

维护数组 las[]，其中 las[x] 表示元素 x 上一次出现的位置（初始为 0）。这样可以确保每个元素在区间内仅被统计一次（取最右侧的出现位置）。

2. 离线排序查询

将所有查询按照右端点 r 从小到大排序。这样可以按顺序处理每个位置 r，逐步维护当前区间 [1, r] 内的不同元素信息。

3. 树状数组维护有效位置

树状数组用于记录每个位置是否是“有效”的（即该位置的元素在 [1, r] 区间内是第一次出现的）。具体操作如下：

• 遍历到位置 cur 时，若 a[cur] 之前出现过（即 las[a[cur]] > 0），则先将之前的位置 las[a[cur]] 在树状数组中减 1（因为该位置的元素已被当前 cur 位置的元素替代，不再是有效位置）。
• 然后将当前位置 cur 在树状数组中加 1，并更新 las[a[cur]] = cur（标记当前位置为该元素的最新有效位置）。

4. 查询区间不同元素个数

对于每个查询 [l, r]，当处理到其右端点 r 时，树状数组中 [l, r] 区间的和即为该区间内不同元素的个数（因为每个有效位置对应一个唯一的元素）。

复杂度分析

• 排序复杂度：对 m 个查询按右端点排序，时间复杂度为 $O(m \log m)$。
• 树状数组操作：每个元素最多被修改两次（一次删除旧位置，一次添加新位置），每次树状数组操作的时间复杂度为 $O(\log n)$，因此总时间复杂度为 $O(n \log n + m \log n)$。

综上，该算法的时间复杂度为 $O((n + m) \log n)$，能够高效处理本题的数据范围。