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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

3065: 带插入区间K小值 系列题解之一——替罪羊套函数式线段树  

2013-02-23 21:53:26|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题是我出的,题目在这里:

这题有很多做法~

可以在status里面有几个神奇的帐号:
3065: 带插入区间K小值 系列题解之一——替罪羊套线段树 - vfleaking - vfleaking的博客
目前AC了此题,这都是我的马甲~~~各代表了一种我给出的参考解法。
当然也有个悲剧先生:
3065: 带插入区间K小值 系列题解之一——替罪羊套线段树 - vfleaking - vfleaking的博客
也是我给出的参考解法之一,很不幸TLE了。60s的时限不能再放宽了,就当做splay很慢的一个证据警示世人吧……

本篇日志介绍第一种解法:(如果不喜欢这种解法,没关系!可以看后面的日志!)
替罪羊树套函数式线段树

关于替罪羊树的介绍,可以参考我写的论文《对无旋转操作的平衡树的一些探究》

考虑这个序列,我们用一棵平衡树来维护每个元素的位置。同时对于每个结点,记录一个函数式线段树的指针,这个函数式线段树维护的是以此结点为根的子树中,出现了哪些值。
此时遇到了一个问题:平衡树要旋转,岂不是很耗时间?
于是替罪羊树的优点就显现出来了,因为替罪羊树不用旋转!

那么这题就可以用替罪羊树套函数式线段树来解决了。

详细算法:
设最大权值为m。
插入要在沿途的函数式线段树里插入当前要插入的元素。如果失去平衡就像往常一样暴力重建,重建时使用函数式线段树合并的方法,那么重建s个结点的时间复杂度就是O(slogs),均摊分析可知插入的时间复杂度是O(lognlogm)
修改就沿途修改函数式线段树就行了。O(lognlogm)
查询的时候像线段树一样不断分裂区间,这样这个区间就会被分裂成若干棵子树和若干个结点,用个数组记下他们,然后像主席树那样进行“线段树上顺着走”式查询就行了。同一深度被记下来的子树个数和结点个数之和不会超过4,所以时间复杂度是O(lognlogm)。

然后写个基于引用计数的垃圾收集器~不然内存会飞起~写出来之后可以发现其实垃圾收集器也不是很难写嘛……

代码:
  评论这张
 
阅读(5845)| 评论(21)
推荐 转载

历史上的今天

评论

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

页脚

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