E - Store Sales Management Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は、全国にチェーン展開する小売企業の本部で働いています。この企業では、各店舗の売上を一元管理するシステムを運用しています。

全国には N 店舗があり、それぞれ 1 から N までの店舗番号が付けられています。各店舗 i (1 \leq i \leq N) には、初期の売上額 S_i が記録されています。

高橋君は、経営分析のため、以下の 2 種類のクエリを合計 Q 回、与えられた順に処理する必要があります。

  • タイプ 1（1 L R）：店舗番号が L 以上 R 以下であるすべての店舗の売上額の合計、すなわち S_L + S_{L+1} + \cdots + S_R を出力する。
  • タイプ 2（2 X V）：店舗 X の売上額 S_X を V に上書きする。すなわち、S_X \leftarrow V とする。

各タイプ 1 のクエリでは、それ以前のすべてのタイプ 2 のクエリによる変更が反映された状態での売上額の合計を求めます。

高橋君の代わりに、各タイプ 1 のクエリに対する答えを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • タイプ 1 のクエリについて：1 \leq L \leq R \leq N
  • タイプ 2 のクエリについて：1 \leq X \leq N, 0 \leq V \leq 10^9
  • タイプ 1 のクエリは 1 つ以上存在する
  • 入力はすべて整数
  • タイプ 1 のクエリの答えは 64 ビット符号付き整数型に収まることが保証される

入力

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • 1 行目には、店舗の数 N とクエリの数 Q が、スペース区切りで与えられる。
  • 2 行目には、各店舗の初期売上額 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 続く Q 行に、Q 個のクエリが 1 行ずつ与えられる。各クエリは先頭の整数でタイプが区別され、i 番目のクエリ \mathrm{query}_i は以下のいずれかの形式で与えられる。
  • タイプ 1 の場合：1 L R（店舗番号 L 以上 R 以下の売上額の合計を求める）
  • タイプ 2 の場合：2 X V（店舗 X の売上額を V に上書きする）

出力

タイプ 1 のクエリが処理されるたびに、対応する売上額の合計を 1 行に出力せよ。

入力例 1

5 4
10 20 30 40 50
1 1 3
2 2 100
1 1 3
1 2 5

出力例 1

60
140
220

入力例 2

8 7
100 200 300 400 500 600 700 800
1 1 8
1 3 6
2 4 1000
1 3 6
2 1 0
1 1 4
1 1 1

出力例 2

3600
1800
2400
1500
0

入力例 3

10 12
1000000000 500000000 300000000 200000000 100000000 50000000 25000000 12500000 6250000 3125000
1 1 10
1 1 5
2 1 0
1 1 10
2 5 999999999
1 4 7
2 3 0
2 4 0
1 1 10
1 10 10
2 10 1000000000
1 9 10

出力例 3

2196875000
2100000000
1196875000
1274999999
1596874999
3125000
1006250000

Score : 433 pts

Problem Statement

Takahashi works at the headquarters of a retail company that operates a chain of stores nationwide. The company runs a system that centrally manages the sales of each store.

There are N stores nationwide, each assigned a store number from 1 to N. For each store i (1 \leq i \leq N), an initial sales amount S_i is recorded.

For business analysis, Takahashi needs to process a total of Q queries of the following 2 types, in the given order.

  • Type 1 (1 L R): Output the total sales amount of all stores whose store numbers are between L and R inclusive, that is, S_L + S_{L+1} + \cdots + S_R.
  • Type 2 (2 X V): Overwrite the sales amount S_X of store X with V. That is, set S_X \leftarrow V.

For each Type 1 query, the total sales amount should be computed with all changes from previous Type 2 queries already applied.

Please find the answer to each Type 1 query on behalf of Takahashi.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • For Type 1 queries: 1 \leq L \leq R \leq N
  • For Type 2 queries: 1 \leq X \leq N, 0 \leq V \leq 10^9
  • There is at least 1 Type 1 query
  • All input values are integers
  • It is guaranteed that the answers to Type 1 queries fit in a 64-bit signed integer type

Input

N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • The first line contains the number of stores N and the number of queries Q, separated by a space.
  • The second line contains the initial sales amounts S_1, S_2, \ldots, S_N of each store, separated by spaces.
  • The following Q lines each contain one of the Q queries. Each query is distinguished by the leading integer indicating its type. The i-th query \mathrm{query}_i is given in one of the following formats:
  • Type 1: 1 L R (compute the total sales amount of stores with numbers from L to R inclusive)
  • Type 2: 2 X V (overwrite the sales amount of store X with V)

Output

Each time a Type 1 query is processed, output the corresponding total sales amount on a single line.

Sample Input 1

5 4
10 20 30 40 50
1 1 3
2 2 100
1 1 3
1 2 5

Sample Output 1

60
140
220

Sample Input 2

8 7
100 200 300 400 500 600 700 800
1 1 8
1 3 6
2 4 1000
1 3 6
2 1 0
1 1 4
1 1 1

Sample Output 2

3600
1800
2400
1500
0

Sample Input 3

10 12
1000000000 500000000 300000000 200000000 100000000 50000000 25000000 12500000 6250000 3125000
1 1 10
1 1 5
2 1 0
1 1 10
2 5 999999999
1 4 7
2 3 0
2 4 0
1 1 10
1 10 10
2 10 1000000000
1 9 10

Sample Output 3

2196875000
2100000000
1196875000
1274999999
1596874999
3125000
1006250000