洛谷 P14420 [JOISC 2014] 历史的研究 / Historical Research 题解

同 AT_joisc2014_c 歴史の研究 | 更差的阅读体验

阅读之前请确保你知道基本的莫队相关知识。

可以离线的区间查询问题，我们考虑莫队。

记录区间内事件数量。当区间伸长时，直接更新即可。

但是，我们无法快速处理区间缩短时的情况。

这时，需要用到回滚莫队。

将序列进行分块。

若一个询问的 $l$ 与 $r$ 在同一个块内，暴力扫描；如果这次询问 $l$ 所属的块与上次 $l$ 所属的块不一样，那将莫队当前的 $l$ 重置到现在 $l$ 所属块的右端点，$r$ 重置到右端点减一；若以上两种情况都不满足，直接伸长区间回答询问，回答完后回滚莫队区间左端点到询问 $l$ 所属块的右端点。

设块长为 $b$，暴力扫描复杂度是 $\mathcal{O}(b)$。

对于其他情况，右端点移动是 $\mathcal{O}(n)$ 的，左端点移动则是 $\mathcal{O}(b)$ 的。

在 $b = \frac{n}{\sqrt(m)}$ 时复杂度最优，为 $\mathcal{O}(n\sqrt{m})$