概述:
莫队是一个十分简单好用的离线区间查询算法, 但它偶尔也会遇到一些问题. 比如说某些操作添加容易删除难, 如果使用普通的莫队算法则可能需要在数据操作上下大功夫.
这个时候回滚莫队就有勇武之地了.
回滚莫队的基本思想就是用只使用增操作, 当需要减操作时直接回滚到某个状态然后进行增操作.
实现:
回滚莫队预处理的过程大致与普通莫队一致, 即按左端点的分块编号排序, 如果分块编号一致则按右端点排序.
如果左右端点分块编号一致的话则直接暴力处理, 这样的一次查询时间复杂度也为$O(\sqrt{n})$, 对总的时间复杂度没有影响.
经过上面的两个操作剩下的所有查询左右端点的分块号不一样. 设左端点所在分块的右端点为$br$, 则整个查询区间可以分为两个区间: 左区间$[l,br]$和右区间$[br+1,r]$.
我们对左端点分块号一样的查询分为一组, 两个查询不在同一组则直接重置, 然后只对同一组内的查询进行转移. 根据查询的排序可以保证查询区间的右端点$r$是单调递增的.
右端点递增那右区间的查询就十分好办: 只需要从当前右指针开始往右进行增操作即可.
对于左区间的查询比较麻烦: 如果左端点比当前左指针更小则可以直接向左进行增加元素的操作, 但如果更大怎么办?
回到”回滚”这个词上, 由于右区间的查询比较简单, 我们可以额外保存下右区间的操作情况和查询结果, 当发生左端点比左指针更大的情况, 则直接将操作与结果回滚到右区间, 由于$l < br+1$一定成立, 此时只需要向左进行增加元素的操作即可.