回滚莫队
2026-08-28
简介
回滚莫队用于处理有增加/删除操作的序列,但其中一个操作不好做,另一个好做。
流程
容易观察到,普通莫队中指针移动次数比询问多很多,我们可以把现在撤销的复杂度放到询问上。
具体的,依旧按照 l 的块编号,r 从小到大排序,设当前块为 [L,R],初始时令 l=L−1,r=L 表示空集,显然此时扩展 r 是 O(n) 的,我们主要关注 l。
由于 l 被限制在长度为 S 的区间里,我们依次处理某个询问,在移动指针时保存一下先前的状态,最后回溯,复杂度是 O(S⋅m) 的。
全部加起来,最终复杂度为 O(S⋅m+Sn2),平均一下得到 S=mn,复杂度为 O(nm)。
