P2710 数列

    • 101通过
    • 407提交
  • 题目提供者 snakes
  • 评测方式 云端评测
  • 标签 平衡树 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    维护一个数列,共7种操作:

    1 INSERT x n a1 a2 .. An

    在第x个数后插入n个数分别为a1 .. an;

    2 DELETE x n

    删除第x个数开始的n个数;

    3 REVERSE x n

    翻转第x个数开始的n个数的区间;

    4 MAKE-SAME x n t

    将第x个数开始的n个数统一改为t;

    5 GET-SUM x n

    输出第x个数开始的n个数的和;

    6 GET x

    输出第x个数的值;

    7 MAX-SUM x n

    输出第x个数开始的n个数的最大连续子序列和。

    输入输出格式

    输入格式:

    第1行为N,M,N表示初始序列中数的个数,M表示操作的个数。

    第2行为N个数a1 .. An,表示初始序列。

    第3行到第M+2行,每行一个操作。

    输出格式:

    输出5 GET-SUM,6 GET,7 MAX-SUM操作的结果。

    输入输出样例

    输入样例#1: 复制
    9 8
    2 -6 3 5 1 -5 -3 6 3
    GET-SUM 5 4
    MAX-SUM 1 9
    INSERT 8 3 -5 7 2
    DELETE 12 1
    MAKE-SAME 3 3 2
    REVERSE 3 6
    GET 5
    MAX-SUM 1 11
    输出样例#1: 复制
    -1
    10
    -5
    10

    说明

    共20组数据,每组数据随机生成,保证每个时刻数列里的数不超过200000个,任何一个输入的数字均在-1000~1000之间,结果不超过2^30。

    第1~2组1≤N≤51≤M≤10

    第3~4组1≤N≤101≤M≤20

    第5~6组1≤N≤201≤M≤50

    第7~8组1≤N≤501≤M≤100

    第9~10组1≤N≤1001≤M≤500

    第11~12组1≤N≤10001≤M≤1000

    第13~14组1≤N≤50001≤M≤2000

    第15~16组1≤N≤100001≤M≤5000

    第17~18组1≤N≤1000001≤M≤10000

    第19~20组1≤N≤2000001≤M≤20000

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