← 返回题目列表

AtCoder · awc0032_e

E. 多重奖金

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

分数: 466 分

问题陈述

高桥是一名部门经理,负责管理 N 员工。每个员工都分配有一个员工编号 1 to N,以及员工的初步评价分 i 是 S_i.

让 T_i 表示员工当前的评价分 i。最初, T_i = S_i (1 \leq i \leq N).

这家公司有一套独特的评价体系。当某个员工 k (1 \leq k \leq N) 作为班组长取得成绩,该成绩对应的奖励积分将添加到所有员工人数为 倍数的员工的评价分中 k (k, 2k, 3k, \ldots)并且最多 N。自从 k 本身是以下的倍数 k,它包含在目标中。

高桥表演 Q 在此评估系统上进行操作。每个操作都是以下两种类型之一:

  • 操作 1:给定一个正整数 k (1 \leq k \leq N) 和一个正整数 v。添加 v 给评价积分 所有员工的 T_j 占所有员工的 j 其员工人数是以下倍数 k 并且最多 N (即 j = k, 2k, 3k, \ldots 和 j \leq N).
  • 操作 2:给定一个正整数 x (1 \leq x \leq N)。输出员工当前评价分之和 1 致员工 x: \displaystyle\sum_{i=1}^{x} T_i.

对于类型的所有操作 2,输出正确答案。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq S_i \leq 10^9
  • 运行中 1, 1 \leq k \leq N
  • 运行中 1, 1 \leq v \leq 10^9
  • 运行中 2, 1 \leq x \leq N
  • 操作 2 至少给出一次
  • 所有输入值均为整数
  • 保证输出的值最多为 2^{63} - 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 行每行包含一个操作。
  • 用于操作 1:以格式给出 1 k v.
  • 用于操作 2:以格式给出 2 x.

输出

每次操作 给定 2 ,输出员工评价分之和 1 致员工 x 一行。


样本输入 1

5 6
1 2 3 4 5
2 3
1 2 10
2 5
1 1 1
2 1
2 4

示例输出 1

6
35
2
34

示例输入 2

4 7
5 1 4 2
1 4 7
2 4
1 3 2
2 2
1 1 5
2 3
2 1

示例输出 2

19
6
27
10

示例输入 3

12 10
3 1 4 1 5 9 2 6 5 3 5 8
2 6
1 3 4
2 12
1 5 7
2 10
1 2 1
1 12 100
2 12
2 1
2 11

示例输出 3

23
68
65
188
3
75

示例输入 4

20 14
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200
2 20
1 4 25
1 6 10
2 12
1 1 3
2 5
1 10 100
2 20
1 7 8
1 20 50
2 19
2 20
1 3 6
2 18

示例输出 4

2100
875
190
2515
2203
2581
2046

示例输入 5

1 4
1000000000
2 1
1 1 1000000000
2 1
2 1

示例输出 5

1000000000
2000000000
2000000000