First Query Problem

题目描述

给定一个整数 $N$ 和长度为 $N$ 的数列 $A=(A _ 1,A _ 2,\ldots,A _ N)$。 给出 $Q$ 个查询，按给定顺序处理它们。 每个查询为以下两种类型之一：

$1 k x$ ：将值 $A _ k$ 设为 $x$。 $2 k$ ：输出值 $A _ k$。

输入格式

输入从标准输入按以下格式给出： $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$ 个此类查询的响应。

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

3
5
0
8
1

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
16
0
0
16
100

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

478
317
838
838
176
595
468

提示

$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$ 对于所有第一类查询。 至少存在一个第二类查询。 输入中的所有数值均为整数。最初，$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$。

标签: AtCoder|abc283B

来源

AtCoder|abc283B