分数: 433 分
问题陈述
高桥在一家零售公司的总部工作,该公司在全国范围内经营连锁店。该公司运行一个集中管理每个商店销售的系统。
有 N 全国门店,每家分配一个门店编号 1 to N.对于每个商店 i (1 \leq i \leq N),初始销售额 记录了 S_i 。
对于业务分析,Takahashi 总共需要处理 Q 以下查询 2 类型,按给定顺序。
- 类型 1 (
1 L R):输出店铺号在之间的所有店铺的总销售额 L 和 R 包括在内,即 S_L + S_{L+1} + \cdots + S_R. - 类型 2 (
2 X V): 覆盖销售额 商店的 S_X 商店的 X 与 V。即设定 S_X \leftarrow V.
对于每个类型 1 查询,应使用已应用的先前类型 2 查询的所有更改来计算总销售额。
请代表 Takahashi 查找每个类型 1 查询的答案。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 对于类型 1 查询: 1 \leq L \leq R \leq N
- 对于类型 2 查询: 1 \leq X \leq N, 0 \leq V \leq 10^9
- 至少有 1 类型 1 查询
- 所有输入值均为整数
- 保证类型 1 查询的答案符合 64- 位有符号整数类型
输入
N Q
S_1 S_2 \ldots S_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
- 第一行包含商店数量 N 和查询数量 Q,用空格分隔。
- 第二行包含初始销售额 每个商店的 S_1, S_2, \ldots, S_N ,以空格分隔。
- 以下 Q 行每包含一个 Q 查询。每个查询都通过指示其类型的前导整数来区分。 i第一个查询 \mathrm{query}_i 采用以下格式之一给出:
- 类型 1:
1 L R(计算以下数字的商店的总销售额 L to R (含) - 类型 2:
2 X V(覆盖商店的销售额 X 与 V)
输出
每次处理类型 1 查询时,在单行上输出相应的总销售额。
示例输入 1
5 4 10 20 30 40 50 1 1 3 2 2 100 1 1 3 1 2 5
示例输出 1
60 140 220
示例输入 2
8 7 100 200 300 400 500 600 700 800 1 1 8 1 3 6 2 4 1000 1 3 6 2 1 0 1 1 4 1 1 1
示例输出 2
3600 1800 2400 1500 0
示例输入 3
10 12 1000000000 500000000 300000000 200000000 100000000 50000000 25000000 12500000 6250000 3125000 1 1 10 1 1 5 2 1 0 1 1 10 2 5 999999999 1 4 7 2 3 0 2 4 0 1 1 10 1 10 10 2 10 1000000000 1 9 10
示例输出 3
2196875000 2100000000 1196875000 1274999999 1596874999 3125000 1006250000