这篇主要介绍在序列上的无修改以及带修改的离线莫队算法。

简介

莫队算法是一个充满着暴力美学的算法。

莫队算法主要是用来解决一些离线无修改的区间查询问题，实现起来相比比较的简单。而莫队算法的主要用在线段树等数据结构无法在很短时间内实现区间信息合并的情况。

莫队算法

核心思想

首先莫队算法的使用情景在上面已经提及。那么接下来让我们以一个实例来理解莫队算法。

有一个正整数序列$A$，$m$次询问在$[l,r]$区间内有多少个不同的数。(HH的项链)

一般来说，我们会想到使用线段树，但这种情况下，我们并不能很快（比如$O(1)$ ）的完成两个区间信息的合并，所以说线段树在这里是起不了作用的。

但是，我们注意到，如果采用适当的方法，我们可以在常数时间内由$[l,r]$区间得到$[l-1,r]$和$[l,r+1]$的信息，只需要记录一下这个数出现的次数，然后增加的时候判一下是否为空即可。同理，略加思考，我们也可以发现从$[l,r]$区间得到$[l+1,r]$和$[l,r-1]$的信息的方法。

所以如果我们直接对左端点排序，然后暴力转移的话，那么这个算法的时间复杂度在最坏情况下是$O(n^2)$的。

这个时候就要用莫队的思想来简化这个时间复杂度。

我们注意到，在$O(n^2)$算法中，每一次的左右端点最坏要移动$n$次。能不能想一个办法，让这个移动次数变小呢？如果通过某种方法排序后，能够使得某些相邻的查询移动变小，那么我们可以优化时间复杂度。但同时注意到，优化了一个移动的同时，会导致那些被排除出上文提到的相邻的查询之间的移动变大一些。所以事实上我们是在寻求一个平衡。

我们可以采用分块的办法。假设我们的分块大小是$Q$,那么应该一共有$\frac{n}{Q}$个块。分块之后，按照左端点所在的块的序号为第一关键字，右端点的位置为第二关键字排序。这句话很重要，其实就是莫队的核心实现吧。

然后，暴力转移。

然后可以注意到，不论是在同一个块内的移动，还是跨块的移动，左端点最多转移的次数是在$Q$的级别的，一共$m$次查询，那么总共转移$mQ$次。而右端点的移动，在一个块内的时候，由于肯定是单调递增，所以每查询过一个块，左端点转移$n$次，一共有$\frac{n}{Q}$个块，所以右端点的移动总共就是$\frac{n^2}{Q}$次。

总共合起来，时间复杂度就是$O(T\times(\frac{n^2}{Q}+mQ))$，T为一次状态转移的时间。利用一些基础复杂的数学知识，可以发现当$Q = \sqrt{n}$的时候，这个式子的值最小，是$O(T\times(m+n)\sqrt{n})$，这也就是基础莫队算法的时间复杂度。不过在具体实现中，精确的$\sqrt{n}$未必就是最快的，有可能需要乘个常数啥的。不过大致是吧。

具体实现

莫队的实现超级简单。不过我因为我太蒻了，开始还是没有想明白。其实就是先扩大，后缩小，一个一个暴力转移。

代码如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//ql,qr 为查询区间，l,r为当前区间
//add 和 del 是自定义的转移函数
//注意自增自减的时间
while(ql<l)
    add(--l);
while(r<qr)
    add(++r);
while(l<ql)
    del(l++);
while(qr<r)
    del(r--);

超级简单吧！

值的一提的是，在我去北京冬令营的时候，台上的神犇说：

莫队的卡常有个小技巧：你奇数的右端点正序排，偶数的右端点逆序排，就可以压掉一半的常数了！

听起来很有道理，但我没有试过。

例题

「SDOI2009」HH的项链-莫队or树状数组

[国家集训队]小Z的袜子 （题解待补

带修改莫队算法

待修改的莫队就是可以支持一些简单的修改的莫队算法。

核心思想

基本上与前面的基础算法类似。假设这里的修改有$t$次。这里的排序一般是分块之后，按照左端点所在的块的序号为第一关键字，右端点所在的块的序号为第二关键字，更改的次数为第三关键字排序。

这里我们取分块的大小为$n^{\frac{2}{3}}$，那么有$n^{\frac{1}{3}}$个块，可以算出算法的时间复杂度是$O(T \times n^{\frac{5}{3}})$。（然而并不太懂怎么推出来这个的…哪位巨佬知道请教一下 非常感谢

具体实现

类似，不写了。

1

//一段时间复杂度为O(n^5/3)的代码。

需要注意，如果单点修改有一个小技巧，就是每次不是更改成待更改数，而是swap当前数和待更改数，这样就可以简单的做更改了。

例题

「国家集训队」数颜色-带修改莫队