D - All Assign Point Add Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。

Q 個のクエリが与えられるので、順番にすべて処理してください。 q 番目 (1\leq q\leq Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。

  • 1\ x _ q ： A のすべての要素に x _ q を代入する。
  • 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) のクエリが 2 番目もしくは 3 番目の形式のとき、1 \leq i _ q \leq N
  • q 番目 (1\leq q\leq Q) のクエリが 1 番目もしくは 2 番目の形式のとき、0 \leq x _ q \leq 10^9
  • 3 番目の形式のクエリが存在する
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

ただし、\operatorname{query}_q は q 番目のクエリであり、1 x, 2 i x, 3 i の形式のいずれかで与えられる。

出力

\operatorname{query}_q が 3 番目の形式であるような q\ (1\leq q\leq Q) の個数を X として、X 行出力せよ。 j\ (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 を出力します。
  • A_3 に 4 を加えます。A=(3,1,8,1,5) となります。
  • A_3=8 なので、8 を出力します。
  • A の要素すべてに 1 を代入します。A=(1,1,1,1,1) となります。
  • A_3 に 4 を加えます。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\operatorname{bit} 整数に収まらない可能性があることに注意してください。

入力例 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

Score : 400 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Given Q queries, process all of them in order. The q-th (1\leq q\leq Q) query is in one of the following three formats, which represents the following queries:

  • 1\ x _ q: assign x_q to every element of A.
  • 2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
  • 3\ i _ q: print the value of A _ {i _ q}.

Constraints

  • 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)
  • If the q-th (1\leq q\leq Q) query is in the second or third format, 1 \leq i _ q \leq N.
  • If the q-th (1\leq q\leq Q) query is in the first or second format, 0 \leq x _ q \leq 10^9.
  • There exists a query in the third format.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Here, \operatorname{query}_q denotes the q-th query, which is in one of following formats: 1 x, 2 i x, and 3 i.

Output

Print X lines, where X is the number of q's (1\leq q\leq Q) such that \operatorname{query}_q is in the third format. The j-th (1\leq j\leq X) line should contain the answer to the j-th such query.

Sample Input 1

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

Sample Output 1

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.

Sample Input 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

Sample Output 2

8000000000

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

Sample Input 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

Sample Output 3

7
5
7
21
21
19
10