NOI2005维修数列

2014年7月30日3,93623

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

题解

这是一道经典的splay模板题

入门建议阅读《伸展树的基本操作与应用》,以及手画练习

以下模板是结合前人经验,经多次修改后的结果

c分别是结点左右儿子,fa是结点父亲

size是子树大小,sum是子树权值和,v是结点权值,mx是当前子树的最大子串和

lx是一个子树以最左端为起点向右延伸的最大子串和,rx类似

tag是结点的修改标记,修改值为v,rev是翻转标记

 

  1. 学长求解释一下Build函数的具体过程和数组的作用,我现在Splay唯一不懂的就是建树,旋转什么的都已经会了,就这个不理解,蛋疼死了。(LCT的Splay不用建树,直接access,splay就好。。于是就没学建树)

  2. 黄学长,可以给新手加一点温暖吗? :比如写一下 注入 v[],tag[],sum[],lx[],rx[]….这些数组的意义 QAQ