Gty 的妹子序列题解

思路

使用 Mo 算法调整当前的位置区间。维护每个值在当前区间内的出现次数；当某个值的次数从零变为一或从一变为零时，在值域 Fenwick 树的对应位置加一或减一。于是任意值域 $[a,b]$ 中出现过的不同值个数，就是 Fenwick 树在该区间的和。

把询问按左端点块编号排序；相邻左块使用相反的右端点顺序，减少指针往返。块长根据 $n$ 与询问数取 $\max(1,\lfloor n/\sqrt m\rfloor)$，适合询问数远大于序列长度的情形。

做法

1. 保存所有询问及原编号，按 Mo 顺序排序。
2. 用左右指针维护当前 $[L,R]$；加入或删除一个位置时更新该值频次。
3. 值频次跨过零时同步更新值域 Fenwick 树。
4. 对询问 $[a,b]$ 查询 Fenwick 区间和，并按原编号输出。

证明

任意时刻，频次数组准确记录当前 $[L,R]$ 中各值出现次数。Fenwick 树在值 $x$ 处为一，当且仅当该频次为正，因此其 $[a,b]$ 区间和正好等于当前位置区间内、值域位于 $[a,b]$ 的不同值个数。Mo 指针最终把当前区间变为每个询问的 $[l,r]$，故记录的答案正确。排序只改变处理顺序，不改变上述不变量。

复杂度

设 Mo 指针移动总次数为 $M$。每次移动进行一次 $O(\log n)$ 的值域更新，每个询问进行两次 Fenwick 前缀查询，时间复杂度为 $O((M+m)\log n)$，空间复杂度为 $O(n+m)$。