中午的时候突然想起NOI2005的维护序列,于是就写了8小时搞出来,3小时写,5小时调,效率真够低的...

这是个很麻烦的问题,我用Splay解决的,首先题目要求的操作有6种,

其中翻转,求最大和比较麻烦.

1. 对于insert操作,效仿NOI2003的文本编辑器,我直接建了一颗几乎平衡的二叉树,然后塞到Splay中相应的位置(这样快一点点)
2. delete操作比较简单,找到相应的子树,删去即可.
3. MakeSame操作:用delta表示要改变成什么,并传递这个值,每次改变delta都覆盖原有的,注意,如果没有delta值,是不能传递或是更改的,否则就会出错,所以我用了一个极小的常量NA表示没有delta值
4. reverse操作:刚看过去感觉有点奇怪,稍稍思考一下发现reverse操作可以像MakeSame操作那样传递(翻转操作其实就是某棵树中所有的子树位值取反一下(左子树放右边,右子树放左边)),然后向下传递就行了
5. GetSum也好做,用Sum记录该子树的和,每次MakeSame或者是进行Splay操作后维护一下就好了(Sum=左子树的Sum+右子树的Sum+1)
6. MaxSum这个比较不好做,但是之前遇到在过线段树上比这个还要麻烦的问题(求某区间所有子串和的和...),就很容易想到了,即LMax表示某子树构成的序列中最大的前缀和是多少RMax表示最大的后缀和是多少,Max_Sum就表示最大子串和是多少,Max_Sum根据LMax和RMax算出就行了

Splay的两个维护函数:deliver()和maintain()

deliver()负责传递树根信息(翻转和MakeSame)

maintain()负责维护Splay的正确性(重新计算相关信息如Sum,LMax...)

我写了6K的代码,花了我很长的时间,然而并没有结束,因为明天还有继续优化代码和算法结构,以便下次再遇到能很快的写出.