← 返回题目列表

AtCoder · abc278_d

G. 所有分配点添加

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

分数: 400 点

问题陈述

给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N.

鉴于 Q 查询,按顺序处理所有查询。 的 q-th (1\leq q\leq Q) 查询采用以下三种格式之一,代表以下查询:

  • 1\ x _ q:分配 x_q 到每个元素 A.
  • 2\ i _ q\ x _ q:添加 x_q to A _ {i _ q}.
  • 3\ i _ q:打印值 A _ {i _ q}.

约束

  • 1 \leq N \leq 2\times10^5
  • 1 \leq Q \leq 2\times10^5
  • 0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
  • 如果 q-th (1\leq q\leq Q) 查询采用第二种或第三种格式, 1 \leq i _ q \leq N.
  • 如果 q-th (1\leq q\leq Q) 查询采用第一种或第二种格式, 0 \leq x _ q \leq 10^9.
  • 存在第三种格式的查询。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

在这里, \operatorname{query}_q 表示 q-th 查询,采用以下格式之一: 1 x, 2 i x,和 3 i.

输出

打印 X 行,其中 X 是数量 q的 (1\leq q\leq Q) 这样 \operatorname{query}_q 是第三种格式。 的 j-th (1\leq j\leq X) 行应包含以下问题的答案 j-第一个这样的查询。


示例输入 1

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

示例输出 1

1
8
5

最初, A=(3,1,4,1,5)。 查询处理如下:

  • A_2=1,所以打印 1.
  • 添加 4 to A_3, 制作 A=(3,1,8,1,5).
  • A_3=8,所以打印 8.
  • 分配 1 到每个元素 A, 制作 A=(1,1,1,1,1).
  • 添加 4 to A_3, 制作 A=(1,1,5,1,1).
  • A_3=5,所以打印 5.

示例输入 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

示例输出 2

8000000000

请注意,元素 A 可能不适合 32位整数类型。


示例输入 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

示例输出 3

7
5
7
21
21
19
10