分数: 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