P14301 [JOI2023 预选赛 R2] 日本沉没 2 / Japan Sinks 2

日本列岛是一条东西向狭长的群岛。日本列岛被南北方向的边界线划分为 $N$ 个区域，这些区域从西向东依次编号为 $1$ 至 $N$。当前，区域 $i$（$1 \le i \le N$）的海拔为 $A_i\ \text{m}$。 日本列岛上时常刮起强风。强风会引起海浪，导致各区域的海拔按以下方式下降： - 当刮起强度为 $x$ 的西风时，在从西数起的 $x$ 个区域中，所有满足“其西侧不存在比自身海拔更高的区域”的区域，其海拔将减少 $1\ \text{m}$。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \le x$，并对所有满足 $1 \le k < i$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1\ \text{m}$；其他情况下海拔不变。 - 当刮起强度为 $x$ 的东风时，在从东数起的 $x$ 个区域中，所有满足“其东侧不存在比自身海拔更高的区域”的区域，其海拔将减少 $1\ \text{m}$。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \ge N - x + 1$，并对所有满足 $i < k \le N$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1\ \text{m}$；其他情况下海拔不变。 你必须模拟未来 $Q$ 天内发生的事件。第 $j$ 天（$1 \le j \le Q$）将发生以下事件之一： - 若 $T_j = 1$，则刮起强度为 $X_j$ 的西风。 - 若 $T_j = 2$，则刮起强度为 $X_j$ 的东风。 - 若 $T_j = 3$，则报告此时区域 $X_j$ 的海拔。 另外，根据约束条件，保证任意区域的海拔不会变为负数。 现给出当前各区域的海拔，以及未来 $Q$ 天内将发生的事件，请编写一个程序，针对所有 $T_j = 3$ 的日期，输出指定区域的海拔。

输入数据按以下格式给出： $N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $T_1\ X_1$ $T_2\ X_2$ $\vdots$ $T_Q\ X_Q$

对于每一个满足 $T_j = 3$ 的 $j$（$1 \le j \le Q$），请在一行中输出第 $j$ 天时区域 $X_j$ 的海拔（单位：米），以整数形式表示。

### 数据范围 - $1 \le N \le 300\,000$。 - $1 \le Q \le 300\,000$。 - $Q \le A_i \le 10^9$（$1 \le i \le N$）。 - $1 \le T_j \le 3$（$1 \le j \le Q$）。 - $1 \le X_j \le N$（$1 \le j \le Q$）。 - 所有输入值均为整数。 ### 子任务 1. （5 分）$N \le 2\,000$，$Q \le 2\,000$。 2. （27 分）若 $T_j \ne 3$，则 $X_j = N$（$1 \le j \le Q$）。 3. （28 分）$A_1 = A_2 = \cdots = A_N = Q$。 4. （20 分）$T_j \ne 2$（$1 \le j \le Q$）。 5. （20 分）无额外约束。 翻译由 Qwen3-235B 完成。