莫队算法总结

本文章最后修改于2018年5月7日。


写在前面

莫队算法用于离线解决一类区间问题。


普通莫队

如果我们已知查询为区间\([l,r]\)的答案,并且能在\(O(1)\)的时间内通过添加或删除一个元素得到\([l-1,r],[l+1,r],[l,r-1],[l,r+1]\)的答案,那么就可以考虑使用莫队算法。

做法:

1.首先我们对原序列分块,原序列长度\(N\),每块大小记为\(Size\),那么块数为\(\lfloor \frac{N-1}{Size} \rfloor +1\),每块从左到右依次编号。

2.对所有询问\([l_i,r_i]\)以询问左端点所在块的序号为第一关键字,右端点的大小为第二关键字进行排序。按照这样的顺序通过添加或删除元素求解每个询问的答案。

可以证明当\(Size\)取\(\sqrt{N}\)时,总的时间复杂度为\(O(N^{1.5})\)。

  • 左端点在同一块时,右端点是递增的,变化\(N\)次,共有\(\sqrt{N}\)个块,这一部分复杂度为\(O(N^{1.5})\)。
  • 左端点转移到下一块时,右端点最多变化\(N\)次,共有\(\sqrt{N}\)个块,这一部分复杂度为\(O(N^{1.5})\)。
  • 左端点在同一块时,每次最多变化\(\sqrt{N}\),转移到下一块时,最多变化\(2\sqrt{N}\),询问共\(N\)个,这一部分复杂度为\(O(N^{1.5})\)。

模板:


带修改莫队

对于一些带单点修改的问题,还是存在一种莫队姿势的。当然,一次修改要求\(O(1)\)完成。

每个修改操作记录位置和修改前后的值,这样方便还原修改。

每个询问除了记录区间\([l,r]\)之外,还要记录在此询问之前的修改操作个数(也可以叫做时间)\(t\),记\(pos_x\)表示\(x\)所在块的编号。

那么将所有询问按照\((pos_l,pos_r,t)\)做三关键字排序。那么在普通莫队的基础上,再维护一个修改时间就可以了。

可以证明当\(Size\)取\(N^{\frac{2}{3}}\)时,左端点、右端点、以及时间的移动复杂度均为\(O(N^{\frac{5}{3}})\),所以总的时间复杂度为\(O(N^{\frac{5}{3}})\)。

懒得分析了。

模板:

回滚莫队

我们经常会遇到这样一种问题,即插入操作十分简单,但是直接删除却非常困难(举个例子,当你要维护最值时)。有没有一种办法避免删除呢?有的,用回滚莫队的姿势就好了~

回滚,rollback,其实意思应该是还原到修改之前。假设当前询问为\([l,r]\)。\(pos_l\)不变时,右端点一直增加,添加操作好说,和普通莫队一样做,但是左端点怎么办呢?我们可以暂时先不把开头\([l,pos_l\times Size]\)这部分添加,然后先存个档,暴力的插入这一小段,得到当前询问的答案后,再读档还原(有些是撤销修改),这就是回滚操作了。

题目

普通莫队

带修改莫队

回滚莫队

 

不定期更新~