AT_abc342_g [ABC342G] Retroactive Range Chmax

[problemUrl]: https://atcoder.jp/contests/abc342/tasks/abc342_g 長さ $ N $ の整数列 $ A=(A\ _\ 1,A\ _\ 2,\ldots,A\ _\ N) $ が与えられます。 $ Q $ 個の操作を順に処理してください。 操作は次の $ 3 $ 種類のいずれかです。 - タイプ $ 1 $ の操作は整数の $ 3 $ つ組 $ (l,r,x) $ で表され、$ i=l,l+1,\ldots,r $ に対して、$ A\ _\ i $ を $ \max\lbrace\ A\ _\ i,x\rbrace $ で置き換えることに対応する。 - タイプ $ 2 $ の操作は整数 $ i $ で表され、$ i $ 回目の操作を取り消すことに対応する（ただし、$ i $ 回目の操作はタイプ $ 1 $ の操作であり、これまでに取り消されていないことが保証される）。数列 $ A $ は、最初の状態からはじめてこれまでのタイプ $ 1 $ の操作のうち**取り消されていない**操作がすべて行われた状態になる。 - タイプ $ 3 $ の操作は整数 $ i $ で表され、現在の $ A\ _\ i $ の値を出力することに対応する。

N/A

N/A

### 制約 - $ 1\leq\ N\leq2\times10\ ^\ 5 $ - $ 1\leq\ A\ _\ i\leq10\ ^\ 9\ (1\leq\ i\leq\ N) $ - $ 1\leq\ Q\leq2\times10\ ^\ 5 $ - タイプ $ 1 $ の操作において、$ 1\leq\ l\leq\ r\leq\ N $ かつ $ 1\leq\ x\leq10\ ^\ 9 $ - タイプ $ 2 $ の操作において、$ i $ はそれ以前に与えられた操作の回数以下かつ $ 1\leq\ i $ - タイプ $ 2 $ の操作において、$ i $ 番目の操作はタイプ $ 1 $ の操作 - タイプ $ 2 $ の操作における $ i $ は重複しない - タイプ $ 3 $ の操作において、$ 1\leq\ i\leq\ N $ - 入力はすべて整数 ### Sample Explanation 1 はじめ、数列 $ A $ は $ (2,7,1,8,2,8) $ です。 $ 1,2,3 $ 回目の操作では $ A\ _\ 1,A\ _\ 3,A\ _\ 4 $ の値である $ 2,1,8 $ をそれぞれ出力してください。 $ 4 $ 回目の操作では $ A\ _\ 1,A\ _\ 2,A\ _\ 3,A\ _\ 4,A\ _\ 5 $ の値を $ \max\lbrace\ A\ _\ i,4\rbrace $ で置き換えます。 この操作の直後、$ A $ は $ (4,7,4,8,4,8) $ となります。 $ 5,6,7 $ 回目の操作ではこの時点での $ A\ _\ 1,A\ _\ 3,A\ _\ 4 $ の値である $ 4,4,8 $ をそれぞれ出力してください。 $ 8 $ 回目の操作では $ A\ _\ 3,A\ _\ 4,A\ _\ 5,A\ _\ 6 $ の値を $ \max\lbrace\ A\ _\ i,9\rbrace $ で置き換えます。 この操作の直後、$ A $ は $ (4,7,9,9,9,9) $ となります。 $ 9,10,11 $ 回目の操作ではこの時点での $ A\ _\ 1,A\ _\ 3,A\ _\ 4 $ の値である $ 4,9,9 $ をそれぞれ出力してください。 $ 12 $ 回目の操作では $ 4 $ 回目の操作を取り消します。 この操作の直後、$ A $ は $ (2,7,9,9,9,9) $ となります。 $ 13,14,15 $ 回目の操作ではこの時点での $ A\ _\ 1,A\ _\ 3,A\ _\ 4 $ の値である $ 2,9,9 $ をそれぞれ出力してください。