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$行，每行一个操作，格式见题目描述 ## 输出格式 输出若干行，每行一个整数，表示查询区间的最大子段和 ## 数据规模 对于 $100\%$ 的数据，保证 $1\le N\le 10^5,1\le Q\le 10^5,0\le|A_i|\le 10^4,0\le|x|\le 10^4$ 感谢@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.

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

8
3
6
3
5