Operations on a Matrix

题目描述

我们有一个 $N \times M$ 的矩阵，初始所有元素均为 $0$。 处理给定的 $Q$ 个查询。每个查询为以下格式之一。

$1 l r x$ ：将 $x$ 加到第 $l$ 列、第 $(l+1)$ 列、…、第 $r$ 列的每个元素上。 $2 i x$：将第 $i$ 行的每个元素替换为 $x$。 $3 i j$：输出第 $(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$ 的查询，输出一行包含答案。

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
2
2
5
3
4

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

9000000000

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

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$ 的查询。 输入中的所有数值均为整数。矩阵的变化如下所示。 $\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}$

标签: AtCoder|abc253F

来源

AtCoder|abc253F