首页 > 代码库 > bzoj1500(妥妥的splay模板题)

bzoj1500(妥妥的splay模板题)

1500: [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 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

Sample Output

-1
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模板题)