最大部分和サブアレイ (Maximum Sum Subarray)
与えられたのは、
n 個の整数が入った配列と、q 個のクエリです。クエリには 2 種類があり、1 つはインデックス p の要素を更新するもの、もう 1 つは区間 [l; r] の中で最大部分和サブアレイを求めるものです。区間
[l; r] における最大部分和サブアレイとは、その区間の中で連続した部分配列の要素の合計が最大となるものを指します。つまり、区間 [l; r] に含まれる連続したサブアレイ [l'; r'] の要素の合計が最大になる値を求める問題です。入力
最初の行には、2 つの整数
n と q が与えられます (1 ≤ n, q ≤ 100 000)。次の行には、
n 個の整数 a_1, a_2, ..., a_n がスペース区切りで与えられます (各要素の値は -10^9 以上 10^9 以下)。続く
q 行にはクエリが与えられます。クエリの形式は、1 l r (1 ≤ l ≤ r ≤ n) または 2 p x (1 ≤ p ≤ n, -10^9 ≤ x ≤ 10^9) です。[l; r]内で最大部分和サブアレイを求める。
- インデックス
pの要素をxに更新する。
出力
クエリのうち、タイプ 1 (最大部分和サブアレイを求める) のものに対して、結果を出力します。
例
Input | Output |
8 4
-2 1 -3 4 -7 2 1 -5
1 2 6
2 5 0
1 2 6
1 1 2 | 4
6
1 |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB