NOI2005维修数列

2014年7月30日5,64724

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是翻转标记

 

  • zld37949552014年7月31日 上午1:21 回复

    给用数组写Splay的黄学长跪烂烂。。

    #1  
    • smkx2014年7月31日 上午7:26 回复

      splay还能怎么写?

      #11
      • hzwer2014年7月31日 上午9:47 回复
        admin

        听他意思估计是指针23333

        #12
  • lyx2015年3月13日 上午8:42 回复

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

    #2  
    • hzwer2015年3月14日 上午7:45 回复
      admin

      实际上就是把一个序列递归建成二叉树T T。。。我这个代码写的繁琐了

      #21
      • lyx2015年3月20日 下午8:08 回复

        有同感- -不太好记,不过感觉Splay和Rotate写的很优美,一下就记着了。PS:缩行看起来不是很习惯QAQ

        #22
  • HBH2015年4月7日 下午4:05 回复

    处理rev标记的时候为什么不需要交换ch [0]和ch ?

    #3  
    • HBH2015年4月7日 下午4:30 回复

      哦。。之前处理过了

      #31
  • 嗯哼2015年4月7日 下午7:20 回复

    黄学长为什么不用处理0号节点咩?在pushup()的时候不会更新错么?

    #4  
    • hzwer2015年4月7日 下午8:51 回复
      admin

      mx[0]=-inf;

      #41
  • LYK2015年4月10日 下午1:27 回复

    测试了下pushdown中的pushup是没有必要的。

    #5  
  • Devin2015年4月13日 下午3:50 回复

    学长,如果要让splay跑得快一点,可以往什么方向改进呢 QAQ

    #6  
    • hzwer2015年4月13日 下午4:41 回复
      admin

      指针版。?反正我不会

      #61
      • Starzxy2015年4月14日 下午4:33 回复

        指针确实快比较多但是代码量要多一倍的样子QAQ

        #62
        • lowsfish2015年4月14日 下午7:41 回复

          代码量并不会多。。而且可读性更高

          #63
          • Starzxy2015年4月15日 下午8:18

            我这种一用指针写5k+的是不是没救了。。

            #64
          • Recursion2015年4月15日 下午9:10

            我还是觉得指针用起来舒服多了

            #64
          • shanquan22015年4月15日 下午11:12

            不应该是数组舒服吗

            #64
        • HansBug2015年4月15日 下午8:27 回复

          额。。。表示以前常用指针写各种树结构代码坑爹的一塌糊涂而且经常滚粗了还半天找不出来= =,直到后来统统改用数组

          #63
  • hao2016年10月31日 下午3:18 回复

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

    #7  
    • qwq2016年11月1日 上午1:28 回复

      我觉得你学一下splay再看这题会比较好= =

      #71
    • hzwer2016年11月3日 下午9:30 回复
      admin

      已加

      #71
  • 斯巴达临时工2017年2月4日 下午10:31 回复

    黄学长,请问第164行的mx[0]=-inf有什么作用?

    #8