UNTITLE1 - Untitled Problem II

题意翻译

给你一个数组 $a_n$ ( $|a_i| \le 10^4$ , $n \le 5 \cdot 10^4$ ) 记 $s_n$ 是它的前缀和,即 $s_i = \sum_{j = 1}^i a_j$ 。 接下来进行 $m$ 组操作,分别有以下2种: 1. 输入 $0\ x\ y\ k$ ,表示将 $x \le i \le y$ 中的 $a_i$ 值都加上 $k$ 。( $|k| \le 10^4$ , $1 \le x \le y \le n$ ) 2. 输入 $1\ x\ y$ ,表示查询 $\max_{x \le i \le y} s_i$ 。( $1 \le x \le y \le n$ ) 输入顺序:先输入 $n$ ,再输入每个 $a_i$ 的值,再输入 $m$ ,再输入 $m$ 组对应的询问。 感谢@EntropyIncreaser 提供的翻译

题目描述

You are given a sequence of N integers A $ _{1} $ , A $ _{2} $ .. A $ _{N} $ . (-10000 <= A $ _{i} $ <= 10000, N <= 50000) Let S $ _{i} $ denote the sum of A $ _{1} $ ..A $ _{i} $ . You need to apply M (M <= 50000) operations: - 0 x y k: increase all integers from A $ _{x} $ to A $ _{y} $ by k(1 <= x <= y <= N, -10000 <= k <= 10000). - 1 x y: ask for max{ S $ _{i} $ | x <= i <= y }.(1 <= x <= y <= N)

输入输出格式

输入格式


- In the first line there is an integer N. - The following line contains N integers that represent the sequence. - The third line contains an integer M denotes the number of operations. - In the next M lines, each line contains an operation "0 x y k" or "1 x y".

输出格式


For each "1 x y" operation, print one integer representing its result.

输入输出样例

输入样例 #1

5
238 -9622 5181 202 -6943
5
1 3 4
0 5 5 4846
1 3 5
0 3 5 -7471
1 3 3

输出样例 #1

-4001
-4001
-11674