← 返回题目列表

AtCoder · joi2023_yo2_e

E. 日本沉没 2

中文机器翻译题面 查看原题

配点: 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).
  • 所有输入值都是整数。

小課題

  1. (5 点) N \leqq 2\,000,Q \leqq 2\,000.
  2. (27 点) T_j \neq 3 如果 X_j = N (1 \leqq j \leqq Q).
  3. (28 点) A_1 = A_2 = \cdots = A_N = Q.
  4. (20 点) T_j \neq 2 (1 \leqq j \leqq Q).
  5. (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 满足约束。