← 返回题目列表

AtCoder · awc0006_e

E. 门店销售管理

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

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