AT_joi2023_yo2_e 日本沈没 2 (Japan Sinks 2)

日本列岛是一个东西向狭长的群岛。日本列岛被南北方向的分界线分成 $N$ 个区块。区块从西到东依次编号为 $1$ 到 $N$。现在，第 $i$ 个区块（$1 \leq i \leq N$）的海拔为 $A_i\:\mathrm{m}$。 在日本列岛上经常会发生暴风雨。每当暴风雨来临时，海浪会导致各区块的海拔按如下方式降低： - 对于强度为 $x$ 的**西风暴风雨**，在从西数不超过 $x$ 个的区块中，所有“在其西侧不存在比自身海拔更高的区块”的区块，其海拔都会减少 $1\:\mathrm{m}$。即，若暴风雨发生前第 $i$ 个区块的海拔为 $a_i$，只有当 $i \leq x$，并且对所有满足 $1 \leq k < i$ 的 $k$ ，$a_k \leq a_i$，此时第 $i$ 个区块海拔减少 $1\:\mathrm{m}$，否则保持不变。 - 对于强度为 $x$ 的**东风暴风雨**，在从东数不超过 $x$ 个的区块中，所有“在其东侧不存在比自身海拔更高的区块”的区块，其海拔都会减少 $1\:\mathrm{m}$。即，若暴风雨发生前第 $i$ 个区块的海拔为 $a_i$，只有当 $i \geq N - x + 1$，并且对所有满足 $i < k \leq N$ 的 $k$，$a_k \leq a_i$，此时第 $i$ 个区块海拔减少 $1\:\mathrm{m}$，否则保持不变。 你需要模拟接下来 $Q$ 天内发生的事件。第 $j$ 天（$1 \leq j \leq 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$ $\dots$ $A_N$ $T_1$ $X_1$ $T_2$ $X_2$ $\vdots$ $T_Q$ $X_Q$

对于每一个 $T_j = 3$ 的 $j$（$1 \leq j \leq Q$），按顺序每行输出第 $j$ 天时指定区块的海拔（单位：$\mathrm{m}$）。

## 子任务 1.（$5$ 分）$N \leq 2\,000$，$Q \leq 2\,000$。 2.（$27$ 分）若 $T_j \neq 3$，则 $X_j = N$（$1 \leq j \leq Q$）。 3.（$28$ 分）$A_1 = A_2 = \cdots = A_N = Q$。 4.（$20$ 分）不存在 $T_j = 2$（$1 \leq j \leq Q$）。 5.（$20$ 分）无其他额外限制。 ## 样例解释 1 区块 $1,2,3,4,5$ 的海拔 $[m]$ | 事件 | 处理后各区块海拔 | | ----------- | ---------------------- | | 初始 | $7, 7, 7, 7, 7$ | | 第1天 持续强度为3的西风暴风雨 | 西面前3个区块中，没有更西侧比本身更高的区块的是 1,2,3 区块 → $6, 6, 6, 7, 7$ | | 第2天 持续强度为1的西风暴风雨 | 西面第1个区块中，没有更西侧比本身更高的区块是 1 区块 → $5, 6, 6, 7, 7$ | | 第3天 查询1号区块的海拔 | $5$ | | 第4天 持续强度为1的东风暴风雨 | 东面第1个区块中，没有更东侧比本身更高的区块是 5 区块 → $5, 6, 6, 7, 6$ | | 第5天 持续强度为5的东风暴风雨 | 东面前5个区块中，没有更东侧比本身更高的区块是 4,5 区块 → $5, 6, 6, 6, 5$ | | 第6天 查询2号区块的海拔 | $6$ | | 第7天 查询4号区块的海拔 | $6$ | 本样例满足子任务 $1, 3, 5$ 的限制条件。 ## 样例解释 2 本样例满足子任务 $1, 2, 5$ 的限制条件。 ## 样例解释 3 本样例满足子任务 $1, 4, 5$ 的限制条件。 ## 样例解释 4 本样例满足子任务 $1, 5$ 的限制条件。 # 数据范围与限制 - $1 \leq N \leq 300\,000$。 - $1 \leq Q \leq 300\,000$。 - $Q \leq A_i \leq 10^9$（$1 \leq i \leq N$）。 - $1 \leq T_j \leq 3$（$1 \leq j \leq Q$）。 - $1 \leq X_j \leq N$（$1 \leq j \leq Q$）。 - 输入数据均为整数。 由 ChatGPT 5 翻译