首页 > 代码库 > bzoj1500(妥妥的splay模板题)
bzoj1500(妥妥的splay模板题)
1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 6366 Solved: 1910
[Submit][Status]
Description
Input
输入文件的第1行包含两个数N和M,N表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
HINT
题意:RT
思路:比较好的splay模板题,基本上这题过了,splay的基本操作也就掌握的差不多了,包括向下更新,翻转,这里我在整个序列上增加了两个节点,一端一个,这样可以方便
区间操作,A完这题感觉整个人都傻逼了,其实代码能力怎么样一写这种代码长的题目就检测出来了,感觉要提高代码能力要经常写这些代码老长老长的题~
这里讲一讲怎样用splay提取一段区间,新手看看吧,大神可以一笑而过~~
假设splay所维护的整个区间长度为n,实际长度为n+2,因为开始的时候在左端设置了0节点,在右端设置了n+1节点,设置这两个节点是为了方便区间的提取操作
假设要提取区间[L,R],可以先将第L-1个节点旋转到根,然后再将第R+1个节点旋转到第L-1个节点的下面,现在第R+1个节点的左孩子所覆盖的区间就是[L,R],怎么
样,是不是很简单了,其实我觉得splay的关键操作就三个,1.将j节点旋转到i节点的下面,2.旋转操作,3.区间提取,然后其它的操作像什么push up,push down就
类似于线段树了~
有了区间提取操作做基础以后,现在可以任意插入一段区间,任意删除一段区间,求任意区间的信息(和,最大值等等)
1.在pos位置后面插入一段区间,先将第pos节点旋转到根,再将第pos+1节点旋转到pos节点的下面,现在第pos+1节点一定没有左子树,然后将要插入的区间作为其左
子树,这里可以将要插入的区间先建成一棵平衡树再插入,效率会高一点
2.将[L,R]区间删除,先将第L-1节点旋转到根,再将第R+1节点旋转到L-1节点的下面,然后将R+1节点的左子树赋为null即可
3.查询区间的信息也一样
4.有一点要注意的是,在对整棵splay做修改之后要及时的从修改的地方旋转到根,这就类似于线段树在修改任意一段区间以后要及时的push up操作
难点基本都已攻破,细节看代码,包括push down,push up ,旋转,splay,翻转,得到第k大的节点,得到一段区间等等~
<script src="https://code.csdn.net/snippets/464034.js" type="text/javascript"></script>
bzoj1500(妥妥的splay模板题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。