TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3884
  • 题目
  • P3884平衡树 NOI2005维修数列
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    输入格式

    第1行包含两个数N和M,N表示初始时数列中数的个数,M表示要进行的操作数目。
    第2行包含N个数字,描述初始时的数列。
    以下M行,每行一条命令,格式参见问题描述中的表格。

    输出格式

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

    样例输入

    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

    样例输出

    -1
    10
    1
    10

    提示

    你可以认为在任何时刻,数列中至少有 1 个数。 输入数据一定是正确的,即指定位置的数在数列中一定存在。 
     
    50%的数据中,任何时刻数列中最多含有 30 000 个数; 100%的数据中,任何时刻数列中最多含有 500 000 个数。 
     
    100%的数据中,任何时刻数列中任何一个数字均在[-1 000, 1 000]内。 100%的数据中,M ≤20 000,插入的数字总数不超过 4 000 000 个,输入文件 大小不超过 20MBytes。 


    来源  noi2005