A59 - RSQ (Range Sum Queries) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) があり、最初はすべての要素が 0 になっています。以下の 2 種類のクエリを処理してください。

  • クエリ 1：A_{\mathrm{pos}} の値を x に更新する。
  • クエリ 2：A_l, A_{l+1}, \ldots, A_{r-1} の合計値を答える。

ただし、与えられるクエリの数は全部で Q 個であるとします。

制約

  • 入力はすべて整数である
  • 1 \leq N \leq 100000
  • 1 \leq Q \leq 100000
  • 1 \leq \mathrm{pos} \leq N
  • 0 \leq x \leq 1000
  • 1 \leq l < r \leq N + 1

入力

入力は以下の形式で標準入力から与えられます。

N Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

i 番目のクエリ \mathrm{Query}_i では、まずクエリの種類 c_i（1 または 2）が与えられます。c_i = 1 の場合は \mathrm{pos}, x が、c_i = 2 の場合は l, r が追加で与えられます。

すなわち、各クエリは以下に示す 2 つの形式のいずれかです。

1 \mathrm{pos} x

2 l r

出力

クエリ 2 の答えを、順番に出力してください。

入力例 1

8 4
1 3 16
1 6 24
2 4 8
2 1 7

出力例 1

24
40
  • はじめ、A = (0, 0, 0, 0, 0, 0, 0, 0) です。
  • 1 個目のクエリでは、A_3 の値を 16 に更新します。A = (0, 0, 16, 0, 0, 0, 0, 0) となります。
  • 2 個目のクエリでは、A_6 の値を 24 に更新します。A = (0, 0, 16, 0, 0, 24, 0, 0) となります。
  • 3 個目のクエリでは、(A_4, A_5, A_6, A_7) = (0, 0, 24, 0) の合計値 24 を出力します。
  • 4 個目のクエリでは、(A_1, A_2, A_3, A_4, A_5, A_6) = (0, 0, 16, 0, 24, 0) の合計値 40 を出力します。