MyException - 我的异常网
当前位置:我的异常网» 编程 » 莫队算法总结(Markdown版)

莫队算法总结(Markdown版)

www.MyException.Cn  网友分享于:2015-02-11  浏览:0次
莫队算法小结(Markdown版)

wtf,最近挖坑有点小多啊,没办法>_<容我先把糖果公园A了再来写这个吧= =看看今天能不能A掉

好吧,我承认我第二天才把糖果公园A掉>_<下面把这篇小结补上

首先众所周知的是莫队算法是要把询问先按左端点属于的块排序,再按右端点排序

复杂度就先不证了,有兴趣的同学可以自己YY下或者查阅资料

下面举几个例子详细说明


1.小Z的袜子

Description:

给定一个序列m个询问

每次询问:

区间中选两个数,两个数相等的概率

若概率为0则输出01

仔细观察发现,令x表示x这个值出现的次数,则每次询问[l,r]区间时答案就是

(x2)(rl+12)

假如我们知道[l,r]区间中每个x出现的次数,用cntx表示,用ans表示当前答案

那么我们可以考虑当我们从[l,r]变为[l,r+1]时对ans的影响

已知只有ar这个值的变化影响着我们的答案,而且容易看出答案是

ans=anscntar(cntar1)

cntar=cntar+1

ans=ans+cntar(cntar1)

想一想为什么

其他情况同理请自行思考

这样每次转移均是O(1),总复杂度O(n1.5)

Code

2.Codeforces 86D(Yandex.Algorithm 2011)

几乎和小Z的袜子一模一样的莫队模板题

Code

3.bzoj 3289(Mato的文件管理)

Description

给定一个序列m个询问

每次询问:

区间中逆序对数

很显然的发现可以用树状数组+莫队艹过去,每次修改是O(nlogn)的,可以通过

Code

这些题基本上都是一个套路了,学了莫队基本就会了

因为每次查询都是一个连续的区间,我们可以轻易找到每移动一次后对答案的贡献

那么,如果不是正常的对序列的区间询问,而是对树上两点路径的询问该怎么办呢?

没错,这就是传说中的。。。

树上莫队

先举个例子

1.Spoj 10707 Count on a tree II(COT2)

Description

给定一棵树上n个结点上的数值,m个询问

每次询问:

区间中不同值的个数

卧槽,这TM怎么做啊?区间不是连续的啊!这莫队是不是做不了啊?

莫慌,我们有个神奇的东西,叫做

dfs序

我们可以用时间戳来对每个节点进行标记,$l_x$,$r_x$分别表示$x$的进出时间

我们利用了dfs序的性质,可以把两点间路径转换为一个连续的区间(还需要考虑Lca的问题,想一想,为什么)

没错,这样我们便可以对dfs序进行分块,莫队一样搞!

神犇们看到现在的话应该会做了,蒟蒻还是继续详细的说做法把>_<

定义S(u,v)uv路径上的顶点集合,root表示根节点

S(u,v)=S(root,u)S(root,v)lca(u,v) (表示集合中的对称差)

定义T(u,v)=S(root,u)S(root,v),我们先不管lca的事情

如果我们从uv的路径变成uv的路径的话对答案有什么影响呢?

根据定义我们可以得到T(u,v)=S(root,u)S(root,v)

T(u,v)T(u,v)=S(root,u)S(root,v)S(root,u)S(root,v)

=S(root,v)S(root,v)

=T(v,v)

于是我们可以得到T(u,v)=T(u,v)T(v,v)

即每次更新时T(v,v)即可

也即对v-v’的路径(除了lca(v,v))的点的存在性取反即可

实际上我们记录的是T,然后每次改变lca(v,v’)的存在性将其变为S统计答案

然后再将lca(v,v)的存在性还原变回T就行了

其实读者可以换个图把dfs序标一下帮助理解>_<

然后这题实际已经解决了,将dfs序分块就将区间化为dfs序上区间问题,考虑lca就可以了

Code

2.WC 2013 糖果公园(Uoj 58)

Description

唔。。题目太长了童鞋们自己看吧>_<戳这里

总之它是需要修改的啦~

好了,想必看到这里,大家对莫队算法和树上莫队算法都已经有了一定的了解

我们发现之前我们做的题都是只有查询没有修改,那么有修改的就不可以做了吗?

并非如此

如果没有修改我们随意搞搞就可以了,有修改的话相等于加了一个时间的维度变成了三维的

我们可以按左端点为第一关键字,右端点为第二关键字,时间为第三关键字排序

预处理每次修改前的颜色,以及这次修改后的颜色

莫队对询问排序

每次询问发现与上次时间不同时暴力t++,t–同时修改颜色及答案即可(用到之前预处理)

然后解决完时间问题后便就是正常的二维莫队了

如果我们将块的大小设为B=n23,分为n13

相当于询问分成了nB2块,每次移动距离为B,每块最多移动n

由于n和q同阶,所以总复杂度是O(nB+nnB2)所以得到B=n23最优

然后就是拍代码啦~

Code

完结撒花!

(妈蛋从10点多写到现在总算是写完了,感人肺腑,意识不清可能哪里写错了,多多包涵>_<

文章评论

如何成为一名黑客
如何成为一名黑客
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
我的丈夫是个程序员
我的丈夫是个程序员
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为什么程序员都是夜猫子
为什么程序员都是夜猫子
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员必看的十大电影
程序员必看的十大电影
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员应该关注的一些事儿
程序员应该关注的一些事儿
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
中美印日四国程序员比较
中美印日四国程序员比较
漫画:程序员的工作
漫画:程序员的工作
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员都该阅读的书
程序员都该阅读的书
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
我是如何打败拖延症的
我是如何打败拖延症的
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老程序员的下场
老程序员的下场
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员的鄙视链
程序员的鄙视链
程序员和编码员之间的区别
程序员和编码员之间的区别
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
鲜为人知的编程真相
鲜为人知的编程真相
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
一个程序员的时间管理
一个程序员的时间管理
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
Java程序员必看电影
Java程序员必看电影
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
旅行,写作,编程
旅行,写作,编程
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
10个调试和排错的小建议
10个调试和排错的小建议
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
那些争议最大的编程观点
那些争议最大的编程观点
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有