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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

3065: 带插入区间K小值 系列题解之四——根号大军  

2013-02-28 23:00:40|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本篇日志介绍次优解决方案:(如果所有解法都不喜欢,没关系!可以无视掉这道题!)
带根号的算法

【块状链表套线段树】
看标题知算法……每个块里维护个线段树,代表这个块里出现的数值。然后……啊……是吧……
不多说了……大家都懂……查询还是照例在线段树上走一走~
O(logm * sqrt(n)) (m是权值最大值)
常数巨大……

【朝鲜树套函数式线段树】
嘛……布吉岛朝鲜树是神马的……可以去看我写的论文……
这个算法跟替罪羊树套函数式线段树类似了……非常暴力……就是不用写垃圾收集器了……因为每次重建可以把整个内存池给清空。
O(logm * sqrt(n))(m是权值最大值)
我估摸着应该这家伙比块状链表跑得快,于是写了个这个版本的程序,光荣TLE。

嘿嘿……也就是说以上说的两个算法都是不能A的。

【将询问分块】
也就是说根号的算法的末日到了?
没有!!!!!
刚才带O(sqrt(n))的,不妨换一种思路,把根号戴在q头上。(q是询问次数)
每操作一段时间就暴力重建出函数式线段树前缀和,新来的插入和查询用一个数组暴力记下来。询问也乱搞下。
这个是Seter的AC方法,详细可以看Seter的题解:http://psr.2333333.tk/
orz Seter……跑得比O(lognlogm)的还快……碾压标程……


暂时这篇题解就是最终话了。
除此之外,我目前不知道还有什么神奇的有效算法了。
很有可能未来的某一天,有人会用我没提到的新的神奇方法AC此题。
vfk将持续关注。
  评论这张
 
阅读(2194)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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