D - LRUD Instructions

壁を行と列にわけて保存し、移動方向に合わせて直近の壁を二分探索する、という手法は典型と言えると思います。

今回は、行及び列が非常に多いので、単純に行または列の番号をインデックスとした二次元配列に壁を保存していくことができません。
公式解説では、mapが遅いなと思うことがあり、座標圧縮で対応しました。しかし、その分、実装が複雑になってしまい手間取りました。

また、壁の記録には自作の平衡二分探索木(スプレー木)を使用しました(値の重複を許す、多重集合で実装しています)。ここでは詳細は書きませんが、「 $x$ 以下／未満の最大値を取得する」という操作をサポートします。
動作は保証できませんが、自由に使用して問題ありません。
Submission #35688615 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)

E - Notebook

木っぽい感じだと思ったのですが、ポインタを使うような問題をあまり見たことがなかったので、ポインタを使用しない実装方法で解きました。

公式解説の補足を見て、永続スタックについて知りましたが、記載する実装方法はポインタを使用していないだけで、内容は永続スタックと同じでした。

永続スタックの参考↓
あなたの庭に永続データ構造を飾りませんか？ - noshi91のメモ

では、実装方法を書きます。

まず、使用する配列や変数です。
- 配列 $V$ ：クエリで追加した値を追加順に保存する
- 変数 $cur$ ：各クエリ処理において、 $A$ の末尾の値が保存されている $V$ のインデックスを保存する
- 配列 $BK$ ： $BK_i$ には $V_i$ が追加される直前の $cur$ が保存されるような配列
- ハッシュマップ $M$ ：ページをkeyとして $cur$ を保存する

$V_0 = -1,\ BK_0 = 0$ と初期化しておきます。これは $A$ が空であることを示す番兵となります。
後述する $cur$ を戻す処理をどれだけ行っても $V_0$ に留まり続けることが可能です。

各クエリの処理です。

ADD x
$V$ の末尾に $x$ を追加します。 $x$ の直前に $A$ の末尾であった値の $V$ のインデックスは $cur$ なので、 $BK$ の末尾に $cur$ を追加します。新たな $cur$ は $V$ の末尾のインデックスとなるよう更新します。
DELETE
現在の $A$ の末尾の値 $V_{cur}$ を削除する代わりに、１つ前に末尾だった値に戻ればよいです。すなわち、 $cur\leftarrow BK_{cur}$ と更新します。
SAVE y
ハッシュマップに $y$ をkeyとして現在の $cur$ を保存します。すなわち、 $M_y \leftarrow cur$ とします。
LOAD z
ハッシュマップに保存した位置となるように $cur$ を更新します。すなわち、 $cur\leftarrow M_z$ とします。なお、保存されていない場合は、 $cur\leftarrow 0$ としておけば良いです。