← 返回题目列表

Codeforces · 1725/K

K. 批评王国

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

Pak Chanek 正在访问一个王国,该王国因其居民经常批评该王国的各个方面而赢得了“批评王国”的绰号。经常受到批评的一方面是建筑物的高度。该王国有 $$$N$$$ 建筑物。最初,建筑物 $$$i$$$ 的高度为 $$$A_i$$$ 单位。

在任何时间点,居民都可以提出新的批评,即他们目前不喜欢高度在$$$l$$$和$$$r$$$单位之间的建筑物,包括两个整数$$$l$$$和$$$r$$$。已知 $$$r-l$$$ 始终为奇数。

在$$$1$$$分钟内,王国建设队可以将任何建筑物的高度增加或减少$$$1$$$单位,只要高度仍然为正数。每次收到居民的当前批评,王国的建筑团队都会在尽可能短的时间内,确保没有高度在 $$$l$$$ 和 $$$r$$$ 单位之间的建筑物。可以看出,只有一种方法可以做到这一点。

注意,施工队只关心目前居民的批评。以前所有的批评都被忘记了。

您必须解决 $$$Q$$$ 查询。每个查询都是以下三种可能性之一:

- 1 k w:王国的建筑团队将建筑物的高度 $$$k$$$ 更改为 $$$w$$$ 单位($$$1 \leq k \leq N$$$、$$$1 \leq w \leq 10^9$$$)。
- 2 k:王国的建筑团队希望你找到建筑物的高度 $$$k$$$ ($$$1 \leq k \leq N$$$)。
- 3 l r:居民目前不喜欢高度在 $$$l$$$ 和 $$$r$$$ 单位之间(含 $$$2 \leq l \leq r \leq 10^9-1$$$,$$$r-l$$$ 为奇数)的建筑物。

请注意,高度的每次更改仍会持续到下一个查询。

输入

第一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 4 \cdot 10^5$$$) — 王国中的建筑物数量。

第二行包含 $$$N$$$ 整数 $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq 10^9$$$) — 建筑物的初始高度。

下一行包含一个整数 $$$Q$$$ ($$$1 \leq Q \leq 4 \cdot 10^5$$$) — 查询数。

接下来的 $$$Q$$$ 行中的第 $$$j$$$ 行包含第 $$$j$$$ 个查询,如所述。至少有一个 $$$2$$$ 类型的查询。

输出

对于 $$$2$$$ 类型的每个查询,输出一行,其中包含表示所询问建筑物高度的整数。

示例

输入 #1

5
2 6 5 6 2
9
1 5 10
2 5
1 1 3
3 3 6
3 8 9
1 2 9
2 3
2 2
2 4

输出 #1

10
7
9
7

注意

经过$$$1$$$-st查询后,每栋建筑的高度为$$$2, 6, 5, 6, 10$$$。

$$$3$$$-rd查询后,每栋建筑的高度为$$$3, 6, 5, 6, 10$$$。

第 $$$4$$$ 次查询后,每个建筑物的高度为 $$$2, 7, 7, 7, 10$$$。

第 $$$5$$$ 次查询后,每个建筑物的高度为 $$$2, 7, 7, 7, 10$$$。

第 $$$6$$$ 次查询后,每个建筑物的高度为 $$$2, 9, 7, 7, 10$$$。