CF1725K Kingdom of Criticism

Pak Chanek 正在拜访一个被称为“批评之国”的王国，因为这里的居民经常批评王国的各个方面。其中一个经常被批评的方面是建筑物的高度。王国中有 $N$ 座建筑物。最初，第 $i$ 座建筑物的高度为 $A_i$ 单位。 在任意时刻，居民们可能会提出新的批评，即他们当前不喜欢高度在 $l$ 到 $r$ 单位之间（包含 $l$ 和 $r$）的建筑物，其中 $l$ 和 $r$ 是两个整数。已知 $r-l$ 总是奇数。 在 $1$ 分钟内，王国的施工队可以将任意一座建筑物的高度增加或减少 $1$ 单位，只要高度仍然为正数。每当收到居民的当前批评时，王国的施工队会以最少的时间让所有建筑物的高度都不在 $l$ 到 $r$ 单位之间（包含 $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$ 单位之间（包含 $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$ 个查询后，每座建筑物的高度为 $2, 6, 5, 6, 10$。 在第 $3$ 个查询后，每座建筑物的高度为 $3, 6, 5, 6, 10$。 在第 $4$ 个查询后，每座建筑物的高度为 $2, 7, 7, 7, 10$。 在第 $5$ 个查询后，每座建筑物的高度为 $2, 7, 7, 7, 10$。 在第 $6$ 个查询后，每座建筑物的高度为 $2, 9, 7, 7, 10$。 由 ChatGPT 4.1 翻译