GSS6 - Can you answer these queries VI

题意翻译

## 题目大意 给出一个由$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