No.1000 Point Add and Array Add

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 151
作問者 : tempura_pptempura_pp / テスター : tsutajtsutaj
18 ProblemId : 3979 / 出題時の順位表
問題文最終更新日: 2020-02-28 06:37:22

問題文

長さ $N$ の数列 $A$ と $B$ があります。$A$ は入力で与えられる数列であり、$B$ は最初すべての要素が $0$ である数列です。
以下の $2$ 種類のクエリが合計で $Q$ 個与えられるので、それらを順にすべて処理したあとの数列 $B$ を求めてください。

  • A $x$ $y$ : $A_x$ に $y$ を足す
  • B $x$ $y$ : $x\leq i\leq y$ をみたす整数 $i$ について、$B_i$ に $A_i$ を足す

入力

$N\ Q$
$A_1\ A_2\ \cdots \ A_N$
$c_1\ x_1\ y_1$
$c_2\ x_2\ y_2$
$\vdots$
$c_Q\ x_Q\ y_Q$

  • 与えられる数はすべて整数
  • $1\leq N, Q\leq 200000$
  • $1\leq A_i \leq 10^9$
  • $c_i$ は 'A', 'B' のいずれか
    • $c_i$ が 'A' のとき、$1\leq x_i \leq N$, $1\leq y_i \leq 100000$
    • $c_i$ が 'B' のとき、$1\leq x_i \leq y_i \leq N$

出力

すべてのクエリを処理した後の数列 $B$ の各要素を順に空白区切りで出力してください。 最後に改行してください。

サンプル

サンプル1
入力
7 3
9 8 1 9 6 10 8
B 2 5
A 7 9
B 4 7
出力
0 8 1 18 12 10 17

  • $1$ つめのクエリで $B$ が ${0, 8, 1, 9, 6, 0, 0}$ になります。
  • $2$ つめのクエリで $A$ が ${9, 8, 1, 9, 6, 10, 17}$ になります。
  • $3$ つめのクエリで $B$ が ${0, 8, 1, 18, 12, 10, 17}$ になります。

サンプル2
入力
10 10
1 4 1 5 9 2 6 5 3 5
A 2 7
A 5 9
B 1 4
B 6 10
A 10 3
B 1 2
A 8 3
B 4 9
A 6 2
B 1 10
出力
3 33 2 15 36 8 18 21 9 13

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。