回滚莫队

__ryp__ · 2024-08-12 19:14:31 · 个人记录

普通的莫队需要我们支持两个操作：加入或删除某点，同时计算贡献。通常，这两个操作的时间是常数或者对数的。

但是有的情况下，我们没法在比较好的时间内同时维护两个操作的贡献。比如说要用莫队求区间的最大值。加点是简单的，删点时我们发现没法知道新的最大值该是多少。

这时候我们就可以用回滚莫队来解决。

我们将询问离线，按照左端点的块编号为第一关键字，右端点升序为第二关键字来排序。此时我们的询问分为：

• 在一个块之内的。这种询问的块长小于等于 B，可以直接暴力

• 跨越多个块。由于左端点块编号相同，因此右端点单增。因此，对于右端点我们可以一直加点。但是左端点不一定单调，但是变化量是小于 B 的。因此我们可以暴力把 L 先移动到左端点，然后再回滚。

这里头我们第二个 L 移动时，贡献单独来算，不影响整个的贡献。这样，我们就能快速实现回滚。