← 返回题目列表

AtCoder · awc0047_c

C. 存钱罐管理

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

分数: 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: 1 L R X (存款 X 日元存入每个存钱罐从 L to R)
  • 类型 2: 2 P (查看存钱罐中的金额 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