浅谈莫队算法

本篇随笔简单讲解一下算法竞赛中的莫队算法。

一、莫队算法的概念及应用

莫队是莫涛。这个名字值得我们铭记一下。涨涨RP。

莫队算法的应用是离线解决一类不带修的区间查询问题。

很多人比如说我，可能会问。说那线段树解决区间问题为什么就不行了呢？换句话说，在什么情况下，(O(Nlog N))的线段树没有(O(Nsqrt N))的莫队有用呢？

这么说，就是当线段树的pushup操作非常难搞的时候，莫队的优势就体现出来了。

比如这样的一个问题：给定一个大小为N的数组，数组中所有元素的大小a[i]<=N。你需要回答M个查询。每个查询的形式是L，R。你需要回答在范围[ L，R ]中至少出现3次的数字的个数。

我们发现，这道题的pushup操作并不能(O(1))来进行，而且巨难维护。所以这个就不行。

然而这个可以拿莫队做。

这就是莫队较之线段树等数据结构的优秀之处。

在我看来，莫队算法的原理主要有二：双指针和分块。

先从暴力开始慢慢思考：假如我们已知一个区间([l,r])的情况，我们用(O(1))的时间能扩展出这个区间外扩1的情况。这个需要一个桶来维护。这样我们的时间复杂度是(O(n^2))的，因为没有修改，只需要扫描所有区间即可。

芜湖，虽然复杂度很炸，但是这作为抛砖引玉，差不多给了我们一个莫队的大体概念：

也就是，维护两个指针，处理完一个询问之后，将两个指针按最近的策略移动到下个询问的区间，在移动的同时类似滑动窗口地统计要统计的信息。

考虑优化。

如何优化呢？

我们可以把询问区间离线下来，按一定的方式排个序，排序之后的策略一定是更优的。现在的问题就是选择一种排序策略。先按左端点排序，然后右端点？

显然，这样的排序方式仍然有可能T飞，一卡就炸，而且几率非常大，都不用怎么构造。

于是莫队想出了莫队的排序方式：先对序列分块。对，就是根号的那个分块。然后以左端点所在块的编号为第一关键字，以右端点位置为第二关键字排序。复杂度就会大大降低。

至于证明，就不是蒟蒻能掌握的了。

根据一顿合理的证明，最后得出总复杂度是(O(Nsqrt N))的。