102535: [AtCoder]ABC253 F - Operations on a Matrix

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

问题描述

我们有一个$N \times 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$

其中$\mathrm{Query}_i$表示第$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