莫队算法详解.pdf

《莫队算法详解.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、莫队算法详解本文翻译自MO’sAlgorithm(Querysquarerootdecomposition)，作者anudeep2011，发表日期为2014-12-28。由于最近碰到一些莫队算法的题目，找到的相关中文资料都比较简略，而这篇英语文章则讲解的比较详细，故翻译成中文与大家分享。由于本人水平有限，错误在所难免，请谅解。下面是译文。我又发现了一个有用，有趣但网上资源非常少的话题。在写作之前，我做了一个小调查，令我惊讶的是，几乎所有的印度程序员都不知道该算法。学习这个很重要，事实上所有的codeforces红名程序员都使

2、用这个算法，比如在div1C题和D题中。在一年半以前没有这方面的题目，但从那时起这类题目的数量就爆发了！我们可以期待这在未来的比赛中会有更多的这类题目。莫队算法详解问题描述复杂度O(N2)的简单的解法一个解决上述问题的算法及其正确性−−对上述算法的复杂性证明-O(√N∗N)上述算法的适用范围习题和示例代码问题描述给定一个大小为N的数组，数组中所有元素的大小<=N。你需要回答M个查询。每个查询的形式是L，R。你需要回答在范围[L，R]中至少重复3次的数字的个数。例如：数组为{1，2，3，1，1，2，1，2，3，1}（索引从0开

3、始）查询：L=0，R=4。答案=1。在范围[L，R]中的值={1，2，3，1，1}，只有1是至少重复3次的。查询：L=1，R=8。答案=2。在范围[L，R]中的值={2，3，1，1，2，1，2，3}，1重复3遍并且2重复3次。至少重复3次的元素数目=答案=2。复杂度O(N2)的简单的解法对于每一个查询，从L至R循环，统计元素出现频率，报告答案。考虑M=N的情况，以下程序在最2坏的情况运行在O（n2）foreachquery:answer=0count[]=0foriin{l..r}:count[array[i]]++ifco

4、unt[array[i]]==3:answer++对上述算法稍作修改。它仍然运行在O（n2）add(position):count[array[position]]++ifcount[array[position]]==3:answer++remove(position):count[array[position]]--ifcount[array[position]]==2:answer--currentL=0currentR=0answer=0count[]=0foreachquery://currentL应当到L,cur

5、rentR应当到RwhilecurrentLL:add(currentL)currentL--whilecurrentRR:remove(currentR)currentR--outputanswer最初我们总是从L至R循环，但现在我们从上一次查询的位置调整到当前的查询的位置。如果上一次的查询是L=3，R=10，则我们在查询结束时有currentL=3、curr

6、entR=10。如果下一个查询是L=5，R=7，则我们将currentL移动到5，currentR移动到7。add函数意味着我们添加该位置的元素到当前集合内，并且更新相应的回答。remove函数意味着我们从当前集合内移除该位置的元素，并且更新相应的回答。一个解决上述问题的算法及其正确性莫队算法仅仅调整我们处理查询的顺序。我们得到了M个查询，我们将把查询以一个特定的顺序进行重新排序，然后处理它们。显然，这是一个离线算法。每个查询都有L和R，我们称呼其为“起−−−−−−点”和“终点”。让我们将给定的输入数组分为√N块。每一块的大

7、小为N/√N=√N。每个“起点”落入其中的一块。每个“终点”也落入其中的一块。如果某查询的“起点”落在第p块中，则该查询属于第p块。该算法将处理第1块中的查询，然后处理−−第2块中的查询，等等，最后直到第√N块。我们已经有一个顺序、查询按照所在的块升序排列。可以有很多的查询属于同一块。从现在开始，我会忽略（其它，译者注，所有括号内斜体同）所有的块，只关注我们如何询问和回答第1块。我们将对所有块做同样的事。（第1块中的）所有查询的“起点”属于第1块，但“终点”可以在包括第1块在内的任何块中。现在让我们按照R值升序的顺序重新排列

8、这些查询。我们也在所有的块中做这个操作。（指每个块块内按R升序排列。）最终的排序是怎样的？所有的询问首先按照所在块的编号升序排列（所在块的编号是指询问的“起点”属于的块）。如果编号相同，则按R值升序排列。例如考虑如下的询问，假设我们会有3个大小为3的块（0-2,3-5,6-8）：{0,3}