首页 > 代码库 > bzoj1500（妥妥的splay模板题）

bzoj1500（妥妥的splay模板题）

2024-07-21 04:23:27   218人阅读

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模板题）


联系
我们