F - Operations on a Matrix Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

縦 N 行、横 M 列の行列があり、はじめ全ての成分は 0 です。

以下のいずれかの形式で表されるクエリを Q 個処理してください。

  • 1 l r x : l 列目、l+1 列目、\ldots、r 列目の成分全てに x を足す。
  • 2 i x : i 行目の成分全てを x で置き換える。
  • 3 i j : (i, j) 成分を出力する。

制約

  • 1 \leq N, M, Q \leq 2 \times 10^5
  • 1 l r x の形式のクエリについて、1 \leq l \leq r \leq M かつ 1 \leq x \leq 10^9
  • 2 i x の形式のクエリについて、1 \leq i \leq N かつ 1 \leq x \leq 10^9
  • 3 i j の形式にクエリについて、1 \leq i \leq N かつ 1 \leq j \leq M
  • 3 i j の形式のクエリが一個以上与えられる
  • 入力は全て整数

入力

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

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

i 番目に与えられるクエリを表す \mathrm{Query}_i は以下のいずれかの形式である。

1 l r x

2 i x

3 i j

出力

3 i j の形式の各クエリについて、答えを一行に出力せよ。

入力例 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

出力例 1

1
2
2
5
3
4

行列は次のように変化します。

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

入力例 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

出力例 2

9000000000

入力例 3

10 10 10
1 1 8 5
2 2 6
3 2 1
3 4 7
1 5 9 7
3 3 2
3 2 8
2 8 10
3 8 8
3 1 10

出力例 3

6
5
5
13
10
0

Score : 500 points

Problem Statement

We have an N \times M matrix, whose elements are initially all 0.

Process Q given queries. Each query is in one of the following formats.

  • 1 l r x : Add x to every element in the l-th, (l+1)-th, \ldots, and r-th column.
  • 2 i x: Replace every element in the i-th row with x.
  • 3 i j: Print the (i, j)-th element.

Constraints

  • 1 \leq N, M, Q \leq 2 \times 10^5
  • Every query is in one of the formats listed in the Problem Statement.
  • For each query in the format 1 l r x, 1 \leq l \leq r \leq M and 1 \leq x \leq 10^9.
  • For each query in the format 2 i x, 1 \leq i \leq N and 1 \leq x \leq 10^9.
  • For each query in the format 3 i j, 1 \leq i \leq N and 1 \leq j \leq M.
  • At least one query in the format 3 i j is given.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

\mathrm{Query}_i, which denotes the i-th query, is in one of the following formats:

1 l r x

2 i x

3 i j

Output

For each query in the format 3 i j, print a single line containing the answer.

Sample Input 1

3 3 9
1 1 2 1
3 2 2
2 3 2
3 3 3
3 3 1
1 2 3 3
3 3 2
3 2 3
3 1 2

Sample Output 1

1
2
2
5
3
4

The matrix transitions as follows.

\begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 2 & 2 & 2 \\ \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 4 & 3 \\ 1 & 4 & 3 \\ 2 & 5 & 5 \\ \end{pmatrix}

Sample Input 2

1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

Sample Output 2

9000000000

Sample Input 3

10 10 10
1 1 8 5
2 2 6
3 2 1
3 4 7
1 5 9 7
3 3 2
3 2 8
2 8 10
3 8 8
3 1 10

Sample Output 3

6
5
5
13
10
0