AC. 梦想

frank_c1

[BZOJ 1500] 维修数列

发布于2015年12月19日 | 1条评论 | 743阅读 | 伸展树,数据结构

题目描述

2016010301

输入格式

输入的第1行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。

输出格式

对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。

题目解析

说实话,splay真是蛮好玩的。虽然有点效率问题而且调试麻烦,但是只要使用得当,姿势正确,功能还是十分强大的。

作为我切的第一道数据结构题,维修数列这道题教我做人……据说这是NOI史上考过最BT的数据结构题,全面考察了splay的各种操作,堪称splay的终极BOSS。我也真是手好,一上来居然就点进了这道题目。好吧,下面说说这道题。

首先我们定义splay上的基本操作 extract(l,r) ,表示提取开区间(l,r),即闭区间[l+1,r-1]到一颗完整的子树中,这样可以方便地统计答案。具体操作是,先将元素l旋转到根,再将元素r旋转到根下。根据平衡树的性质,此时根节点(l)的右儿子(r)的左子树就对应区间[l+1,r-1]。方便起见,我们称这课子树为Ta,其根节点为root(Ta)。

开始之前,不要忘了建一个首结点和尾结点。

操作1,extract(posi,posi+1),此时Ta为空。先递归建一棵小型平衡树,然后把这棵子树作为Ta接上去就可以了。操作2,extract(posi-1,posi+tot),把Ta删掉。由于插入的数可能很多,为了防止爆内存,建议空间回收,即将删掉的结点建一个栈,重复利用。操作3/4,extract(posi-1,posi+tot),在root(Ta)上打标记。向下走时下传标记。在下传标记前,该结点的值就应修改完毕,标记唯一的作用是用来下传。操作5,extract(posi-1,posi+tot),增加一个属性sum,记录子树点权之和。询问时直接输出sum(root(Ta))即可。

本题的重难点在于操作6。最大和子序列在静态或者带修改时都好做,但变成带插入时情况就没那么简单了。这里就运用了splay自身的灵活性。维护四个量,vmax,lmax,rmax,totmax,lmax表示从以该结点为根的子树所代表的区间的左端开始的最大和,rmax表示从区间的右端开始的最大和,totmax表示整一段区间的最大和,这样转移上去就得到最大子序列和(totmax(root(Ta)))。但这里有一个小问题,如果这个序列中的所有值都小于0,那么用这个方法会直接返回0(不取任何元素),然而在这里是不可取的(必须要取一个)。所以还要维护vmax,为子树中最大值,若区间中最大值小于0,则直接返回vmax(root(Ta))。

至此,本题的难点都被解决,只要在实现时细心一点就好。