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