102831: [Atcoder]ABC283 B - First Query Problem

Problem Statement

You are given an integer $N$ and a sequence $A=(A _ 1,A _ 2,\ldots,A _ N)$ of length $N$.

Given $Q$ queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value $A _ k$ to $x$.
• 2 k : print the value $A _ k$.

Constraints

• $1 \leq N \leq 10 ^ 5$
• $1 \leq Q \leq 10 ^ 5$
• $0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)$
• $1\leq k\leq N$ for all queries.
• $0\leq x\leq 10 ^ 9$ for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Input

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

$N$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
$Q$
$\operatorname{query} _ 1$
$\operatorname{query} _ 2$
$\vdots$
$\operatorname{query} _ Q$

Here, $\operatorname{query} _ i$ denotes the $i$-th query, given in one of the following formats:

$1$ $k$ $x$

$2$ $k$

Output

Print $q$ lines, where $q$ is the number of queries of the second kind. The $j$-th $(1\leq j\leq q)$ line should contain the response to the $j$-th such query.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, $A=(1,3,5)$.

• For the $1$-st query, $A=(1,3,5)$, where $A _ 2=3$, so $3$ should be printed.
• For the $2$-nd query, $A=(1,3,5)$, where $A _ 3=5$, so $5$ should be printed.
• The $3$-rd query sets the value $A _ 3$ to $0$, making $A=(1,3,0)$.
• For the $4$-th query, $A=(1,3,0)$, where $A _ 3=0$, so $0$ should be printed.
• The $5$-th query sets the value $A _ 2$ to $8$, making $A=(1,8,0)$.
• For the $6$-th query, $A=(1,8,0)$, where $A _ 2=8$, so $8$ should be printed.
• For the $7$-th query, $A=(1,8,0)$, where $A _ 1=1$, so $1$ should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

问题描述

给你一个整数 $N$ 和一个长度为 $N$ 的序列 $A=(A _ 1,A _ 2,\ldots,A _ N)$。

处理 $Q$ 个查询，按给定顺序处理。 每个查询属于以下两种类型之一：

• 1 k x ：将值 $A _ k$ 设置为 $x$。
• 2 k ：打印值 $A _ k$。

约束条件

• $1 \leq N \leq 10 ^ 5$
• $1 \leq Q \leq 10 ^ 5$
• $0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)$
• 对于所有的查询，$1\leq k\leq N$。
• 对于所有的第一种类型的查询，$0\leq x\leq 10 ^ 9$。
• 至少有一个第二种类型的查询。
• 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出：

$N$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
$Q$
$\operatorname{query} _ 1$
$\operatorname{query} _ 2$
$\vdots$
$\operatorname{query} _ Q$

其中，$\operatorname{query} _ i$ 表示第 $i$ 个查询，格式如下：

$1$ $k$ $x$

$2$ $k$

输出

打印 $q$ 行，其中 $q$ 是第二种类型的查询的数量。 第 $j$ 行（$1\leq j\leq q$）应该包含对第 $j$ 个这种查询的响应。

样例输入 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

样例输出 1

3
5
0
8
1

最初，$A=(1,3,5)$。

• 对于第 $1$ 个查询，$A=(1,3,5)$，其中 $A _ 2=3$，所以应该打印 $3$。
• 对于第 $2$ 个查询，$A=(1,3,5)$，其中 $A _ 3=5$，所以应该打印 $5$。
• 第 $3$ 个查询将值 $A _ 3$ 设置为 $0$，使得 $A=(1,3,0)$。
• 对于第 $4$ 个查询，$A=(1,3,0)$，其中 $A _ 3=0$，所以应该打印 $0$。
• 第 $5$ 个查询将值 $A _ 2$ 设置为 $8$，使得 $A=(1,8,0)$。
• 对于第 $6$ 个查询，$A=(1,8,0)$，其中 $A _ 2=8$，所以应该打印 $8$。
• 对于第 $7$ 个查询，$A=(1,8,0)$，其中 $A _ 1=1$，所以应该打印 $1$。

样例输入 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

样例输出 2

2
16
0
0
16
100

样例输入 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

样例输出 3

478
317
838
838
176
595
468