注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

一个很多莫队算法初学者的误区  

2014-12-31 21:26:11|  分类: 总结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以下内容难度偏易,相信很多人都知道,这里只是给不知道的人看的。

似乎很多人初学莫队的时候,都有小Z的袜子只能用莫队做的误区
(其实我学的时候也是这么以为的)
最近半群里某机器人提到说一般莫队能做的,分块+可持久化线段树/可持久化块状链表都是能做的
OrzOrz!

事实上说的很有道理。
众所周知,莫队算法是处理区间询问问题的一类杀器。
但事实上处理区间询问问题有另一个杀器。
分sqrt(n)块,预处理ans[i][j]表示第i块到第j块的答案。
询问区间[l,r],会空出不超过O(sqrt(n))个冗余元素。暴力计算这些元素的贡献就行了。
莫队算法要求如果已知[l,r]的答案,支持插入一个数,删除一个数。
然而我们这样子分块就只需要支持插入一个数了。

小Z的袜子这题,关键在于知道每个数的出现次数,就能在插入时计算贡献。
直接上这个思想。
假设询问[l,r],可以看做拆成[L1,R1],[L2,R2][L3,R3]三块。
[L2,R2]由ans数组直接算出。
枚举[L1,R1]的每个数x,我们只要知道x出现了几次,就能累加贡献(比如当前出现了cnt[x]次,我就ans+=2cnt[x]+1,++cnt[x]就行了,写莫队也是这么写的)。
暴力的方法是离散化,对每个x开个vector在里面二分就行了。
当然这样子是sqrt(n)log n的。

注意到我们要求的是x在第i块到第j块的答案。
块只有sqrt(n)。
弄个前缀和数组,记sum[i][j]为数字i在前j块出现几次。
这样就是sqrt(n)每次询问了。
没有实现过……不知道和莫队哪个快一些。

再看看区间众数。
莫队的做法是弄一个支持插入一个数,删除一个数的数据结构。
这样子是O(sqrt(n)log n)的。
--------------------------------------------分割线-----------------------------------------------
UPD:
我错了,莫队算法做区间众数是n^1.5的。
方法就是除了开cnt1[i]表示数字i出现了几次,还要开cnt2[i]表示有几个数出现了i次,这样就是O(n^1.5)了(因为插入删除的复杂度是O(1))的
--------------------------------------------分割线-----------------------------------------------
我们看这个做法。
嘛……好像直接就是O(sqrt(n))了。

还有一个好处就是他是在线的。
所以很多强制在线的题不能莫队,但能用这个搞。
比如lyd&shy的作诗,主席的L,COT2

有人可能会觉得,莫队要弄得不一定是维护一个cnt数组啊
也就是说,插入一个数可能带来的贡献不是这么好算的。
因此机器人说可能复杂的题要用可持久化线段树/可持久化块状链表来爆搞?比如COT2,糖果公园什么的?(我很弱,不太清楚这个做法怎么运用到树上)

不过莫队算法是能待修改的(虽然变成了n^(2/3))
但是我记得WC的时候何奇正好像是用的可持久化块状链表做的糖果公园……那个时候我太弱了,什么可持久化啊,块状链表啊,莫队算法啊一个都不知道,所以就没管了。
现在想来估计也是这个算法的扩展才对……我太弱了不知道怎么扩展。
--------------------------------------------分割线-----------------------------------------------
UPD:
待修改也很简单
莫队的修改是n^(5/3)的
我们分块每次是分sqrt(n)块,而修改一个数需要修改ans[i][j],我们就会修改sqrt(n)^2个值。
那么如果我们分块是分n^(1/3),我们修改就是n^(2/3)的了
查询复杂度也是O(n^(2/3))
所以做到了与莫队同阶
--------------------------------------------分割线-----------------------------------------------

反正估计很多人都是知道的……如果有兴趣就在下面回复一下吧,比如这个做法怎么做BZOJ上的COT2,以及怎么待修改
--------------------------------------------分割线-----------------------------------------------
UPD:
树上带修改是这样的.
先假设没有修改,随便用种方法选出sqrt(n)个关键点,然后每个关键点到根的路径上第一个关键点到他的距离不超过sqrt(n)
接下来如法炮制,ans[i][j]表示第i个关键点到第j个关键点的答案,然后统计每个多出来的部分的点的贡献.
要做的是求一个点在某两个关键点的路径上出现了几次,为了不比正解复杂度高的话最好得是O(1)的.
不如改进一下,我们把关键点构成的虚树上的点全都看作关键点.预处理LCA[i][j].
这样子就能O(1)了
修改就分成n^(1/3)块
--------------------------------------------分割线-----------------------------------------------
还有就是,莫队算法和这个分块,由于杀伤力太大,所以一般效率不高。
我在看JZPLCM的题解的时候,GYZ的原话就是算法太过一般化,导致特殊问题难以做到更好。
我一年多前写莫队算法题解的时候,曾说对于只有区间询问的问题,莫队算法几乎是无敌的。
现在看来真是naive,希望大家不要像我一样。
  评论这张
 
阅读(1795)| 评论(11)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017