← 返回题目列表

AtCoder · abc253_f

I. 矩阵运算

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个 N \times M 矩阵,其元素最初都是 0.

流程 Q 给出查询。 每个查询均采用以下格式之一。

  • 1 l r x :添加 x 中的每个元素 l-th, (l+1)-th, \ldots,和 r第列。
  • 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-th 查询采用以下格式之一:

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