← 返回题目列表

AtCoder · abc283_b

C. 第一个查询问题

中文机器翻译题面 查看原题

分数: 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