根号分治 + 根号平衡.
记 $K=3\times 10^5$ ,对于 $\le \sqrt K$ 的模数 $Y$ ,每次加入一个 $X$ 的时候都暴力更新一下它们的答案,就可以 $O(1)$ 回答.
这部分的时间复杂度是 $O(n\sqrt K)$ .
对于 $>\sqrt K$ 的模数 $Y$ ,可知 $\lfloor \frac X Y\rfloor \le \sqrt K$ ,而 $X\bmod Y=X-\lfloor \frac X Y\rfloor\cdot Y$ .
于是每次询问时,可以枚举 $\lfloor \frac X Y\rfloor$ 的值,询问在某段区间 $[L,R]$ 中出现过的最小的 $X$ .
归纳一下,我们需要维护一个集合,要插入 $O(n)$ 个数,查询 $O(n\sqrt K)$ 次某个数的后继.
直接用 set 维护会多一个 log, 考虑根号平衡,实现 $O(\sqrt K)$ 插入, $O(1)$ 询问后继.
对值域分块,对每个位置维护块内的后继,对每个块维护该块右端点的后继即可.
于是这部分的时间复杂度也是 $O(n\sqrt K)$ .
1 | //%std |