分数: 366 分
问题陈述
高桥管理 N 存钱罐。每个存钱罐的编号为 1 to N.
每个存钱罐 i (1 \leq i \leq N) 最初包含 A_i 日元。从现在开始, Q 操作将按顺序执行。每个操作都是以下两种类型之一:
- 类型 1 (存款):正整数 给出了 L, R, X 。押金 X 日元存入每个存钱罐 L, L+1, \ldots, R。也就是说,每个存钱罐中的金额增加了 X 日元。
- 类型 2 (检查):整数 给出了 P 。查看存钱罐中的当前金额 P.
对于每个类型 2 操作,确定存钱罐中当前的金额 P.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 对于类型 1 操作, 1 \leq L \leq R \leq N
- 对于类型 1 操作, 1 \leq X \leq 10^4
- 对于类型 2 操作, 1 \leq P \leq N
- 至少有一个类型 2 操作
- 所有输入值均为整数
- 保证每个类型2操作的答案(输出量)最多为 10^{18}
输入
输入是按以下格式从标准输入给出的。
N Q A_1 A_2 \ldots A_N query_1 query_2 \vdots query_Q
- 第一行包含存钱罐的数量 N 和操作次数 Q,用空格分隔。
- 第二行包含初始金额 每个存钱罐中都有 A_1, A_2, \ldots, A_N ,以空格分隔。
- 以下 Q 行每行包含一项操作的信息 query_1, query_2, \ldots, query_Q。每个的前导整数 query_i 表示操作类型,格式为以下之一:
- 类型 1:
1L R X (存款 X 日元存入每个存钱罐从 L to R) - 类型 2:
2P (查看存钱罐中的金额 P)
输出
对于每个类型 2 操作,输出当前存钱罐中的金额 P 在一行上。
示例输入 1
5 4 10 20 30 40 50 2 3 1 2 4 5 2 3 2 1
示例输出 1
30 35 10
示例输入 2
8 7 100 200 300 400 500 600 700 800 1 1 5 10 1 3 8 20 2 3 2 6 1 1 8 100 2 1 2 8
示例输出 2
330 620 210 920
示例输入 3
10 10 0 1000000000 500 0 999999999 1 2 3 4 5 1 1 10 10000 2 2 1 5 5 3 2 5 1 1 1 1 2 1 1 3 7 100 2 4 2 10 2 7
示例输出 3
1000010000 1000010002 10001 10100 10005 10102