この問題を見て、「何か難しそうなことしている、分からない」と思った方も多くいらっしゃるのではないでしょうか？

公式解説では何か特殊な発想を要求する問題に見えて、解き方が分かり辛いかもしれません。 この解説では、「そもそもこの問題が要求しているものは何か？」「どのように考察すれば解けたか？」の一例を書きます。

まず、ADDとDELETEに着目します。

ADDは末尾への要素追加、DELETEは末尾の要素を削除する操作であり、クエリごとに出力すべき値も末尾の要素です。 従って、これはデータ構造で言えばstackに該当します。

さて、SAVEとLOADについても考えてみましょう。

LOADを行うと、特定のクエリの時点での状態まで巻き戻ることが分かります。従って、これは永続データ構造の説明に他なりません。

従って、この問題は永続スタックを作る問題である、と読み解くことができます。用語さえ分かれば検索できるので、これでこの問題は解けました。

このように、複数のクエリを捌く問題では、それぞれのクエリを捌くにはどのような性質が必要か？を考えると答えに辿り着きやすくなります。

また、データ構造に必要な性質に対して、「この性質が要求されたらこの構造を疑う」という発想を持っておくと良いかもしれません。例えば、区間和クエリが存在するなら累積和やセグメント木のような和の構造が載るデータ構造を疑う、などですね。

今回の場合、永続データ構造はクエリを捌く問題で有用で、「特定の時間のデータを取得したい」という需要がある場合は永続性を疑うと良いです。

(余談ですが、「特定の時間のデータを取得する」方法としてはクエリ先読みと呼ばれる手法もあります。予め、この時間のこのデータが欲しいという情報を求めておいて、対応する時間になったらデータを取得して未来のクエリに渡してあげる手法です)

(余談2: Twitterで見かけたのですが、今回の操作はGitだと思うと木構造が自然に感じるとのこと。確かに？)

(余談3: 永続スタックの実装時、単方向リストを使う場合は初期状態のノードの(値, 直前のノード)を( \(-1\) ,自分自身)にすると例外処理が不要になったり)