配点: 100 点
問題文
日本列岛是一个东西延伸的狭长群岛。日本列岛被南北边界划分。 它分为 N 部分。从西到西 它们的编号最大为 1 如果要将其更改为输出最多为 N 。目前,分部 i (1 \leqq i \leqq N) 的海拔高度是 A_i \: \mathrm{m} 是。
日本列岛经常发生风暴。当暴风雨发生时,由于波浪侵蚀,各部分的标高会降低,如下所示。
- 实力 x 的西风暴风雨中,从西边数起 在 x 个或更少的地块中,“西边不存在比其海拔更高的地块”的所有地块的标高为 1 \: \mathrm{m} 减少。即风暴前的部分 i 的海拔高度 表示为 a_i ,i \leqq x 并且,1 \leqq k \lt i 对于 k 分区 if a_k \leqq a_i 分区如果 i 的海拔高度是 1 \: \mathrm{m} 减少,否则不变。
- 实力 x 的东风暴风雨中,从东边数起 在 x 个或更少的地块中,所有地块的高程“其东边不存在比其高程更高的地块” 1 \: \mathrm{m} 减少。即风暴前的部分 i 的海拔高度 表示为 a_i ,i \geqq N - x + 1 并且,i \lt k \leqq N 对于 k 分区 if a_k \leqq a_i 分区如果 i 的海拔高度是 1 \: \mathrm{m} 减少,否则不变。
你将会 Q 我们必须模拟当天发生的事件。j 日目 (1 \leqq j \leqq Q中发生以下事件。 当
- T_j = 1 时,强度 X_j 发生西风风暴。 发生
- T_j = 2 时,强度 X_j 东风风暴。
- T_j = 3 ,当时的分区 报告 X_j 的海拔高度。
请注意,约束保证任何截面的高程都不会为负。
各断面当前标高和未来标高 Q 由于当天的事件已给出,T_j = 3 编写一个程序来查找某一天指定路段的海拔高度。
制約
- 1 \leqq N \leqq 300\,000.
- 1 \leqq Q \leqq 300\,000.
- Q \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq T_j \leqq 3 (1 \leqq j \leqq Q).
- 1 \leqq X_j \leqq N (1 \leqq j \leqq Q).
- 所有输入值都是整数。
小課題
- (5 点) N \leqq 2\,000,Q \leqq 2\,000.
- (27 点) T_j \neq 3 如果 X_j = N (1 \leqq j \leqq Q).
- (28 点) A_1 = A_2 = \cdots = A_N = Q.
- (20 点) T_j \neq 2 (1 \leqq j \leqq Q).
- (20 点)没有额外的限制。
入力
输入按以下格式给出。
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 \leqq j \leqq Q)对于每个,j 包裹截至当天 X_j 的海拔高度 (\mathrm{m}) 是一个整数,表示1 逐行输出。
入力例 1
5 7 7 7 7 7 7 1 3 1 1 3 1 2 1 2 5 3 2 3 4
出力例 1
5 6 6
| 区画 1, 2, 3, 4, 5 的海拔 (\mathrm{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 \: \mathrm{m} 因此,5 。 | |
| 5, 6, 6, 7, 7 | ||
| 4 日目 | 实力 1 东风风暴。 从东边 1 或更少,并且“在其以东没有海拔比其更高的部分”是一个部分。 5 。 |
|
| 5, 6, 6, 7, 6 | ||
| 5 日目 | 实力 5 东风风暴。 从东边 5 或更少,并且“在其以东没有海拔比其更高的部分”是一个部分。 4, 5 。 |
|
| 5, 6, 6, 6, 5 | ||
| 6 日目 | 区画 2 的当前海拔是 6 \: \mathrm{m} 因此,6 。 | |
| 5, 6, 6, 6, 5 | ||
| 7 日目 | 区画 4 的当前海拔是 6 \: \mathrm{m} 因此,6 。 |
此输入示例是一个小作业。 1, 3, 5 满足约束。
入力例 2
5 7 10 13 14 7 12 1 5 2 5 3 3 3 4 2 5 3 1 3 2
出力例 2
12 7 9 11
此输入示例是一个小作业。 1, 2, 5 满足约束。
入力例 3
5 6 8 6 7 8 9 1 1 3 1 3 5 1 3 3 2 3 3
出力例 3
7 9 6 6
此输入示例是一个小作业。 1, 4, 5 满足约束。
入力例 4
5 6 6 8 6 9 7 2 1 2 4 3 5 1 5 3 4 3 3
出力例 4
5 7 6
此输入示例是一个小作业。 1, 5 满足约束。