SP4487 GSS6 - Can you answer these queries VI

    • 155通过
    • 573提交
  • 题目来源 SPOJ 4487
  • 评测方式 RemoteJudge
  • 标签
  • 难度 NOI/NOI+/CTSC
  • 时空限制 447ms / 1536MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目大意

    给出一个由$N$个整数组成的序列$A$,你需要应用$M$个操作:

    • I p x 在$~p~$处插入插入一个元素$~x~$
    • D p 删除$~p~$处的一个元素
    • R p x 修改$~p~$处元素的值为$~x~$
    • Q l r 查询一个区间$\left[l,r\right]$的最大子段和

    输入格式

    第一行一个数$N$,表示序列的长度

    第二行$N$个数,表示初始序列$A$

    第三行一个数$M$,表示操作的次数

    接下来的$M$行,每行一个操作,格式见题目描述

    输出格式

    输出若干行,每行一个整数,表示查询区间的最大子段和

    感谢@Anoxiacxy 提供的翻译

    题目描述

    Given a sequence A of N (N <= 100000) integers, you have to apply Q (Q <= 100000) operations:

    Insert, delete, replace an element, find the maximum contiguous(non empty) sum in a given interval.

    输入输出格式

    输入格式:

    The first line of the input contains an integer N.
    The following line contains N integers, representing the starting
    sequence A1..AN, (|Ai| <= 10000).

    The third line contains an integer Q. The next Q lines contains the operations in following form:

    I x y: insert element y at position x (between x - 1 and x).
    D x : delete the element at position x.
    R x y: replace element at position x with y.
    Q x y: print max{Ai + Ai+1 + .. + Aj | x <= i <= j <= y}.

    All given positions are valid, and given values are between -10000 and +10000.

    The sequence will never be empty.

    输出格式:

    For each "Q" operation, print an integer(one per line) as described above.

    输入输出样例

    输入样例#1: 复制
    5
    3 -4 3 -1 6
    10
    I 6 2
    Q 3 5
    R 5 -4
    Q 3 5
    D 2
    Q 1 5
    I 2 -10
    Q 1 6
    R 2 -1
    Q 1 6
    
    输出样例#1: 复制
    8
    3
    6
    3
    5
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。