第 4 题 日本沉没 2 (japansinks2)

本题使用文件输入输出：输入文件 japansinks2.in，输出文件 japansinks2.out。

题目描述

日本列岛是一条东西向狭长的群岛。日本列岛被南北方向的边界线划分为 $N$ 个区域。这些区域从西向东依次编号为 $1$ 至 $N$。当前，区域 $i$（$1 \le i \le N$）的海拔为 $A_i$ m。

日本列岛上时常刮起强风。强风会引起海浪，导致各区域的海拔按以下方式下降：

• 当刮起强度为 $x$ 的西风时，在从西数起的 $x$ 个区域中，所有满足「其西侧不存在比自身海拔更高的区域」的区域，其海拔将减少 $1$ m。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \le x$，并对所有满足 $1 \le k < i$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1$ m；其他情况下海拔不变。
• 当刮起强度为 $x$ 的东风时，在从东数起的 $x$ 个区域中，所有满足「其东侧不存在比自身海拔更高的区域」的区域，其海拔将减少 $1$ m。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \ge N - x + 1$，并对所有满足 $i < k \le N$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1$ 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

输入：

5 7
7 7 7 7 7
1 3
1 1
3 1
2 1
2 5
3 2
3 4

输出：

5
6
6

样例 2

输入：

5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

输出：

12
7
9
11

样例 3

输入：

5 6
8 6 7 8 9
1 1
3 1
3 5
1 3
3 2
3 3

输出：

7
9
6
6

样例 4

输入：

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

输出：

5
7
6

提示

数据范围

• $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 2000$, $Q \le 2000$.
2. （27 分）若 $T_j \neq 3$, 则 $X_j = N$（$1 \le j \le Q$）.
3. （28 分）$A_1 = A_2 = \cdots = A_N = Q$.
4. （20 分）$T_j \neq 2$（$1 \le j \le Q$）.
5. （20 分）无额外约束.

翻译由 Qwen3-235B 完成。