首页 > 其他 > 详细

bzoj3110: [Zjoi2013]K大数查询

时间:2016-05-19 19:11:51      阅读:317      评论:0      收藏:0      [点我收藏+]

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3110

题目大意:有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

做法:看到这题,第一想法,树状数组套可持久化线段树,但是这题是区间修改,暴力修改的话感觉上会GG,所以换一种思维,即树套树实现,这题应该是线段树套线段树,一般的线段树套线段树都是外层维护序列中的位置,内层维护权值,但是对于这题来说不好在树中类似BST来二分答案。换一种思维嘛,外层线段树维护权值,内层线段树维护位置,就很好做了,对于修改操作,外层线段树会经过logn个节点,再在内层线段树中使用lazy—tag,每次修改操作时间复杂度,log^2n,动态开点,空间复杂度也为mlog^2n,对于询问操作,在外层线段树上二分即可。

树套树。

bzoj3110: [Zjoi2013]K大数查询

原文:http://www.cnblogs.com/OYzx/p/5509678.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!