D - 全部赋值与增加点

分数：$400$ 分

问题描述

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$。

给定 $Q$ 个操作，按顺序处理每个操作。 第 $q$ 个 $(1\leq q\leq Q)$ 操作的格式有以下三种，表示如下操作：

• $1\ x _ q$: 将 $x_q$ 赋值给 $A$ 的每个元素。
• $2\ i _ q\ x _ q$: 给 $A _ {i _ q}$ 增加 $x_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$ 个操作 $(1\leq q\leq Q)$ 是第二种或第三种格式，则 $1 \leq i _ q \leq N$。
• 如果第 $q$ 个操作 $(1\leq q\leq Q)$ 是第一种或第二种格式，则 $0 \leq x _ q \leq 10^9$。
• 存在一个第三种格式的操作。
• 输入中的所有值都是整数。

输入

输入格式为标准格式，具体如下：

$N$

$A_1$ $A_2$ $\dots$ $A_N$

$Q$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

其中，$\text{query}_q$ 表示第 $q$ 个操作，其格式为 1 x、2 i x 或 3 i。

输出

输出 $X$ 行，$X$ 是满足第 $q$ 个操作是第三种格式的操作的数量。 第 $j$ 行（$1\leq j\leq X$）应包含第 $j$ 个操作的结果。

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

1
8
5

Initially, $A=(3,1,4,1,5)$. The queries are processed as follows:

• $A_2=1$, so print $1$.
• Add $4$ to $A_3$, making $A=(3,1,8,1,5)$.
• $A_3=8$, so print $8$.
• Assign $1$ to every element of $A$, making $A=(1,1,1,1,1)$.
• Add $4$ to $A_3$, making $A=(1,1,5,1,1)$.
• $A_3=5$, so print $5$.

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

8000000000

Note that the elements of $A$ may not fit into a $32$-bit integer type.

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

7
5
7
21
21
19
10