科技网站建设 开题报告,芙蓉区营销型网站建设定制,网页设计制作网站图片,网站漂浮广告怎么做摘要#xff1a; 莫队算法是一个对于区间、树或其他结构离线#xff08;在线#xff09;维护的算法#xff0c;此算法基于一些基本算法#xff0c;例如暴力维护#xff0c;树状数组#xff0c;分块#xff0c;最小曼哈顿距离生成树#xff0c;对其进行揉合从而产生的一…摘要 莫队算法是一个对于区间、树或其他结构离线在线维护的算法此算法基于一些基本算法例如暴力维护树状数组分块最小曼哈顿距离生成树对其进行揉合从而产生的一个简单易懂且短小好写的算法。此算法在很多情况下可以很轻松的切掉一些复杂而且难写的数据结构问题。
关键词 程序设计、算法、算法优化暴力算法分块算法最小曼哈顿距离生成树。 背景 众所周知在OI竞赛、软件的设计中都会要求我们去处理各种各样的棘手的问题而这些问题之中有一大类就是维护问题比如说对于一个序列的维护对于棵二叉或者多叉树的维护……这些问题往往会需要我们去使用一个或多个高端的数据结构复合来完美解决通常题目的代码十分冗长而且出错可能性十分大是广大OIer、Acmer、Coder所害怕的题目。那么有没有一种方法可以既简单又快捷的解决这类问题这类问题中的一大部分呢莫队算法就诞生辣
理论1 序列莫队我们现在有一个长为n的静态的序列对于序列我们有m次查询我们要动态查询l到r之间大于a小于b的数的个数以及种类。遇到了这个问题我们通常需要使用书套树的数据结构即一颗以自平衡二叉查找树为节点的线段树时间复杂度大约是O(mlognlogn)而且由于空间限制我们还必须动态创建线段树的节点这样一来十分难写一些大约要个400-500行调试起来也很困难。这时候我们来考虑暴力算法如果暴力的处理题目中的问题那么复杂度是多少呢这个不难计算对于每个询问我们都要O(n)的时间处理,一共有m个询问那么暴力处理的复杂度就是O(nm)的明显处理问题花费的时间我们是不能接受的。这是我们想到可以交换询问和询问之间的先后次序这样每次询问在前一次询问的基础上转移就可以节省一些时间了。 但是如何重新排列询问之间的顺序是一个问题。我们需要进行一些理论分析。我们再上一个询问的基础上暴力地维护一个询问假设上一个询问询问区间为[l0,r0]这个询问区间为[l,r]那么我们所谓的暴力维护就是先把现有答案的右边界从r0移动到r再把左边界从l0移动到l那么我们的总花费是O(|l-l0||r-r0|)。仔细看一看没错这就是我们的曼哈顿距离的计算公式有了这个思路我们就可以从图形的角度来思考了对于一个询问[l,r]我们可以将它映射为平面上在(l,r)位置的点那么两个询问之间转移的代价就是询问所对应的点之间的曼哈顿距离。有了这一个结论我们便想到可以用最小曼哈顿生成树来处理询问的顺序。由此莫队算法便诞生啦莫队算法就是先将询问抽象成平面上的点然后进行一边最小曼哈顿距离生成树然后按照生成树的顺序来处理询问这样的算法复杂度大约是O(mSqrt(n))的。如此问题便简单了许多。 但是由于最小曼哈顿距离生成树也不是那么的好写所以莫队算法还能再简单一点么我们思考是否可以用一个简单而暴力的算法代替莫队算法呢。很快便能想到分块算法。我们可以使用分块算法来处理询问之间的次序问题。再去看那个询问对应的点所在的平面我们找到它的X轴我们把X轴平均分割成r分然后我们把在一个块内的询问统一先处理不在一个块内的询问我们按照左端点升序右端点升序排序依次处理。这样做有什么好处呢对于m干个询问如果在一个块里面那么处理这些询问花费的复杂度是O(n/r*n*m)如果有两个询问不在一个同一个块里面按照我们之前的排序规则我们把左区间和右区间在块之间移动的次数最多为r*(n/r)*r次那么我们的复杂度就是O(r*(n/r)*r)次经过简单的数学分析我们可以发现rSqrt(n)是时间复杂度最低为O(nSqrt(n))次是可以接受的时间复杂度。这样我们的莫队算法就又简单有强大了。但是在另一些情况下题目会无耻的限定我们可以使用的空间一般不会因为这样高级数据结构的复合也难以解决这样的问题了。那么如果空间被限定了我们应该如何解决问题呢其实很简单 还记得我们之前的r么我们为了求的时间复杂度最小令rSqrt(n),如果我们令rn ^ (2 / 3)那么便是一个时间复杂度和空间复杂度较为平衡的情况这样可以很好的解决问题。
例题 输入数据首先输入两个整数N,Q分别代表序列的长度和询问的个数。这两个数字将单独占据一行并用一个空格分开。输入数据的第二行包含了N个由一个空格分开的正整数代表了整个序列从左向右依次编号为A1, A2……An。接下来Q行每行两个整数i,j表示了一个询问区间。输入数据保证1≤i jN
例题
2038: [2009国家集训队]小Z的袜子(hose)
Description 作为一个生活散漫的人小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天小Z再也无法忍受这恼人的找袜子过程于是他决定听天由命…… 具体来说小Z把这N只袜子从1到N编号然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双甚至不在意两只袜子是否一左一右他却很在意袜子的颜色毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z他有多大的概率抽到两只颜色相同的袜子。当然小Z希望这个概率尽量高所以他可能会询问多个(L,R)以方便自己选择。
Input 输入文件第一行包含两个正整数N和M。N为袜子的数量M为小Z所提的询问的数量。接下来一行包含N个正整数Ci其中Ci表示第i只袜子的颜色相同的颜色用相同的数字表示。再接下来M行每行两个正整数LR表示一个询问。
Output 包含M行对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1否则输出的A/B必须为最简分数。详见样例 【样例解释】
询问1共C(5,2)10种可能其中抽出两个2有1种可能抽出两个3有3种可能概率为(13)/104/102/5。
询问2共C(3,2)3种可能无法抽到颜色相同的袜子概率为0/30/1。
询问3共C(3,2)3种可能均为抽出两个3概率为3/31/1。
注上述C(a, b)表示组合数组合数C(a, b)等价于在a个不同的物品中选取b个的选取方案数。
【数据规模和约定】
30%的数据中 N,M ≤ 5000
60%的数据中 N,M ≤ 25000
100%的数据中 N,M ≤ 500001 ≤ L R ≤ NCi ≤ N。
单个测试点时限2S 对于上述这道题30%的数据我们可以对于每个询问都扫描询问区间中所存在的数然后计算这样单次复杂度是O(N)的但有M的询问总复杂度是OMN。这就显得有点不太能接受了。
但是当我们知道一个询问[l,r]的答案后[l1,r],[l-1,r],[l,r1],[l,r-1]这四个区间的答案可以通过计算做到O(1)的时间内得到
所以我们可以考虑莫队算法分为如下三步。
1、分块
2、把所有询问左端点排序
3、对于左端点在同一块内的询问按右端点排序然后分三种情况统计。
而复杂度正如理论部分所说的一样
一、i与i1在同一块内r单调递增所以r是O(N)的。由于有sqrt(N)块,所以这一部分时间复杂度是Nsqrt(N)。 二、i与i1跨越一块r最多变化n由于有sqrt(N)块所以这一部分时间复杂度是Nsqrt(N) 三、i与i1在同一块内时变化不超过sqrt(N)跨越一块也不会超过2* sqrt(N)不妨看作是sqrt(N)。由于有N个数所以时间复杂度是O(Nsqrt(N)) 可以证明复杂度是O(Nsqrt(N))了 理论2 可现在有很多问题都设置了修改操作对于这类我们我们又该如何处理呢
问题 我们现在有一个长为n的对于序列我们有m次操作操作分为两种
1、询问在[l,r]中抽到两个数字相同的概率
2、把某个位置的数ai改成x
100%的数据中 N,M ≤1000001 ≤ L R ≤ NCi ≤ N。
单个测试点时限10S
我们会发现加上了修改操作后。就没办法直接按照分块来处理解决询问的顺序。
定义B为分块的大小。 首先考虑没有修改操作那么就和理论1中小Z的袜子一样令B sqrt(n) 。把所有询问左端点排序对于左端点在同一块内的询问按右端点排序,然后写莫队算法按顺序扫询问这样是O(n sqrt(n))。如果现在加上修改操作考虑一个询问(l,r)这样是肯定不够的。 于是变成(l,r,ti)ti是询问时的时间即这次询问是第几次操作。把所有询问左端点l排序对于左端点在同一块内的询问按右端点r所在的块排序对右端点r所在块相同的我们再按照时间ti排序。
然后做莫队算法按顺序扫询问时间有时向前有时倒流。这样令B n ^ (2 / 3)因为在每一块中时间最多从1到T改变一次设询问操作p1次修改操作p2次则在最差情况下的时间复杂度是O(p1 n^(2 / 3)p2 *n^(1 / 3)* n^(1 / 3))O(n^(5 / 3))【n与m等价】这在时限下基本是可以得到答案的。 那么还有个遗留的问题如何处理时间。我们只需要记录修改前和修改后该点的值就可以了。 至此这个问题完美解决。
总结 也许莫队是一种看起来复杂度非常高的算法但如果合理地处理好分块的大小和询问的顺序它便可以变成一个极其有效的工具。 辞谢
Vfleaking、莫涛
参考文献
国家集训队命题《小z的袜子》
参考https://blog.csdn.net/lqybzx/article/details/52235761
给出例题bzoj 2038: [2009国家集训队]小Z的袜子(hose)
bzoj 3236: [Ahoi2013]作业
bzoj 3781: 小B的询问 bzoj 3757: 苹果树 bzoj 2453: 维护队列
bzoj 3052: [wc2013]糖果公园 bzoj 2120: 数颜色
2016多校训练Contest6: 1007 This world need more Zhu hdu5799
