AT_abc253_f [ABC253F] Operations on a Matrix

题目描述

有一个纵向 $N$ 行、横向 $M$ 列的矩阵，初始时所有元素均为 $0$。

请处理 $Q$ 个查询，每个查询有以下三种形式之一：

• 1 l r x ：将第 $l$ 列到第 $r$ 列（包括两端）所有元素都加上 $x$。
• 2 i x ：将第 $i$ 行的所有元素都替换为 $x$。
• 3 i j ：输出第 $i$ 行第 $j$ 列的元素值。

输入格式

输入按以下格式从标准输入读入。

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

每个查询 $\mathrm{Query}_i$ 有以下三种格式之一：

$1$ $l$ $r$ $x$

$2$ $i$ $x$

$3$ $i$ $j$

输出格式

对于每个 3 i j 形式的查询，输出对应元素的值，每个答案占一行。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #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

输入 #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

说明/提示

限制条件

• $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 形式的查询
• 输入均为整数

样例说明 1

矩阵的变化如下：

$\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}$

由 ChatGPT 4.1 翻译