莫队学习笔记（2）回滚莫队

普通莫队在左右端点移动的过程中，当加点和删点操作其中一个很容易实现，但是另一个操作不易实现时，我们可以通过特殊方法实现只增加不删除或只删除不增加，这种莫队被称为回滚莫队，以只增加不删除的回滚莫队为例：

将左端点按照所在块的编号为第一关键字升序排序，右端点按照所在的位置为第二关键字升序排序，处理每次询问前都必须要保证左端点在当前询问的左端点所在块的末尾，从而保证只增加不删除。

首先，若当前和上次询问的左端点所在块不同，则将左右端点都移至左端点所在块的末尾。

其次，若当前询问的左右端点都处于同一个块内，则直接暴力求解答案即可。

否则，先将右端点扩展到当前询问的右端点处，然后记下当前的答案，之后再将左端点向左扩展到当前询问的左端点求出答案，最后将左端点回滚到当前询问的左端点所在块的末尾，并将之前左端点向左扩展所修改的信息都还原回去，答案改为之前记下的答案。

不难发现，这样就保证了只增加不删除，并且与普通莫队相比时间复杂度仍为 $O(n\sqrt{q})$，常数也只大了两倍。

对于只删除不增加的回滚莫队，也是类似的方法，只需要略微修改一下即可——右端点按照所在的位置为第二关键字降序排序，处理每次询问前都必须要保证左端点在当前询问的左端点所在块的开头。

题意：给定长为 $n$ 的序列和 $q$ 次询问，每次询问区间带权最大众数（数值与出现次数乘积最大），$1\le n,q\le10^5$，时限 4s。

用普通莫队去做比较难，原因就在于增加时很好维护答案，但是删除时不易维护答案，因此采用只增加不删除的回滚莫队即可。

题意：给定长为 $n$ 的序列和 $m$ 次询问，每次询问区间 $\operatorname{mex}$，$1\le n,m\le2\times10^5$，时限 1s。

题意：

题意：

题意：

题意：

题意：

To be continued...

莫队数据结构学习笔记

相关