E - 日本沈没 2 (Japan Sinks 2) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点： 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 に対して 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 に対して 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 の制約を満たす．