P2042 [NOI2005]维护数列

    • 553通过
    • 2.2K提交
  • 题目提供者shengmingkexue
  • 标签 Splay 平衡树 模拟 NOI系列 2005 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 64MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线‘ _ ’表示实际输入文件中的空格)

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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: 复制
    -1
    10
    1
    10

    说明

    你可以认为在任何时刻,数列中至少有 1 个数。

    输入数据一定是正确的,即指定位置的数在数列中一定存在。

    50%的数据中,任何时刻数列中最多含有 30 000 个数;

    100%的数据中,任何时刻数列中最多含有 500 000 个数。

    100%的数据中,任何时刻数列中任何一个数字均在[-1 000, 1 000]内。

    100%的数据中,M ≤20 000,插入的数字总数不超过 4 000 000 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。