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

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

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

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

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

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

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

将序列进行分块。

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

设块长为，暴力扫描复杂度是。

对于其他情况，右端点移动是的，左端点移动则是的。

在时复杂度最优，为