分数: 200 点
问题陈述
给你一个整数 N 和一个序列 A=(A _ 1,A _ 2,\ldots,A _ N) 长度 N.
鉴于 Q 查询,按给定顺序处理它们。 每个查询属于以下两种类型之一:
1 k x:设置值 A _ k to 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-th (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-st 查询, A=(1,3,5),其中 A _ 2=3,所以 3 。
- 对于 2-nd 查询, A=(1,3,5),其中 A _ 3=5,所以 5 。
- 的 3-rd 查询设置值 A _ 3 to 0, 制作 A=(1,3,0).
- 对于 4第一个查询, A=(1,3,0),其中 A _ 3=0,所以 0 。
- 的 5-第一个查询设置值 A _ 2 to 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