← 返回题目列表

AtCoder · abc453_g

G. 复制查询

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

分数: 600 点

问题陈述

有 N 长度序列 M: A_1,A_2,\dots,A_N。最初,所有序列的所有元素都是 0.
此后, j序列的第一个元素 A_i 表示为 A_{i,j}.

按给定顺序处理以下三种类型的查询, 总共 Q 条查询。

  • 类型 1:覆盖序列 A_{X_i} 带序列 A_{Y_i}。也就是说,对于每个整数 j (1 \le j \le M),更改 A_{X_i,j} to A_{Y_i,j}.
  • 类型 2:更改 Y_i序列的第一个元素 A_{X_i},即 A_{X_i,Y_i}, 至 Z_i.
  • 类型 3:对于序列 A_{X_i},输出元素的总和 L_i-th 通过 R_i-th,即 A_{X_i,L_i}+A_{X_i,L_i+1}+\dots+A_{X_i,R_i}.

约束

  • 1 \le N,M \le 2 \times 10^5
  • 1 \le Q \le 2 \times 10^5
  • 类型 1 查询满足以下约束:
    • 1 \le X_i,Y_i \le N
  • 类型 2 查询满足以下约束:
    • 1 \le X_i \le N
    • 1 \le Y_i \le M
    • 0 \le Z_i \le 10^9
  • 类型 3 查询满足以下约束:
    • 1 \le X_i \le N
    • 1 \le L_i \le R_i \le M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M Q
{\rm Query}_1
{\rm Query}_2
\vdots
{\rm Query}_Q

在这里, {\rm Query}_i 代表 i第一个查询。

A型 1 查询按以下格式给出:

1 X_i Y_i

A型 2 查询按以下格式给出:

2 X_i Y_i Z_i

A型 3 查询按以下格式给出:

3 X_i L_i R_i

输出

对于每种类型 3 查询,输出该查询的答案。 如果没有类型 3 查询,输出应为空。


示例输入 1

4 5 10
2 2 1 2
2 2 2 7
2 2 4 8
1 1 2
2 2 3 1
1 3 2
2 3 2 10
3 1 2 4
3 2 1 4
3 3 2 2

示例输出 1

15
18
10

在此输入中,准备四个长度的序列 5.

  • 在 1st 查询、设置 A_{2,1}=2。此时, A_2=(2,0,0,0,0).
  • 在 2nd查询、设置 A_{2,2}=7。此时, A_2=(2,7,0,0,0).
  • 在 3rd查询,设置 A_{2,4}=8。此时, A_2=(2,7,0,8,0).
  • 在 4第查询,覆盖序列 A_1 带序列 A_2。此时, A_1=(2,7,0,8,0).
  • 在 5第查询、设置 A_{2,3}=1。此时, A_2=(2,7,1,8,0).
  • 在 6第查询,覆盖序列 A_3 带序列 A_2。此时, A_3=(2,7,1,8,0).
  • 在 7第查询、设置 A_{3,2}=10。此时, A_3=(2,10,1,8,0).
  • 在 8第查询,输出 A_{1,2}+A_{1,3}+A_{1,4}=7+0+8=15.
  • 在 9第查询,输出 A_{2,1}+A_{2,2}+A_{2,3}+A_{2,4}=2+7+1+8=18.
  • 在 10第查询,输出 A_{3,2}=10.