题目描述

输入格式

输入的第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))。

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