日本沈没 2 (Japan Sinks 2)

日本列島は東西に細長い列島である．日本列島は南北方向の境界線により \(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\) 行ずつ順に出力せよ．

JOI 2023 · JCIOI · CC BY-SA 4.0