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