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