Alternating Sum
整数を要素とする長さ
n の配列と、合計 q 回のクエリが与えられています。クエリには2種類があり、特定のインデックス p にある要素の値を更新するものと、区間 [l; r] に対して交互和 (alternating sum) を計算するものです。区間
[l; r] の交互和は、「その区間内でインデックスが偶数の要素の合計」から「インデックスが奇数の要素の合計」を引いた値として定義されます。具体的には、もし部分配列 [l; r] の要素が [ $$a_l, a_{l+1}, \dots, a_r$$ ] であるとき、交互和は入力
1 行目に、配列のサイズを表す整数
n とクエリの総数を表す整数 q が与えられます (1 ≤ n, q ≤ )。
2 行目には、配列の要素を表す n 個の整数 が空白区切りで与えられます ()。
続く q 行にはクエリが与えられ、形式は 1 l r または 2 p x のいずれかです。ここで、1 は区間 [l; r] の交互和を求めるクエリ、2 はインデックス p を値 x に更新するクエリを表します (1 ≤ p ≤ n, 1 ≤ x ≤ , 1 ≤ l ≤ r ≤ n)。出力
クエリが種類 2 の場合ごとに、その交互和を1行ずつ出力してください。
例
入力 | 出力 |
8 3
1 2 3 4 5 6 7 8
1 2 6
2 4 9
1 1 8 | 4
-9 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB