問題概要

クエリが$ Q $個、以下の形式で与えられ、最初は空列を1つ持ち、$ 10 ^ 9 $ページあるノートの各ページには空列が初めから入っている。

すべてのクエリを実行するたびに、今の列の最後尾の要素を出力する。空列ならば、-1と出す。

制約: $ Q \in [1, 5 \times 10 ^ 5], x \in [1, 10 ^ 9] $

考察

明らかに愚直だと大量にコピーをせざるを得なくなる。これはメモリも、制限時間も超える。

では、全部コピーが厳しいなら、クエリを先読みして、たかだかX個までしか後続でみられないのならば、保存する列を末尾からX個に縮められるよね？の方針を考えて、必要な分だけコピーを考えてみる。

方針として、後ろから読んでいく。値として、今Xページのデータをロードというコマンドが来たら、これから逆算してセーブコマンドで渡す野に必要な配列の長さを持たせ、これを$ A $とする。

ADD A--1つ足すので、必要なセーブ時に渡す配列の長さを減らせる。
DELETE A++1つ消すので、必要なセーブ時に渡す配列の長さを減らせる。
LOAD X　後ろから見てここでXページからロードされたので、XページにSAVEする際にわかるように、std::mapでSAVEする際の保持するべき配列の長さをメモ。このとき、
- 最低の長さを1にする。なぜならばロードした直後に配列の末尾を知る必要があるので、たとえロードしてADDを連発しても最低でも1つはメモしないとならない。
- すでにXページの必要な長さがYだとわかっている場合、今の必要な長さがY以下ならば、更新しない。
  - LOAD 4, DELETE を5回, LOAD 4, DELETEを5000回のような物の対策
  - 言ってしまえばここがTLEの原因。めちゃくちゃADD, SAVE 1, (LOAD 1, DELETE1回)を10万回, LOAD 1, DELETE10万回とかされると、配列のstd::mapからの全数コピーが何回も出てしまうし、これは根本的には対処のしようがない。
SAVE X　Xページにセーブする必要があるときの長さを、逆算してる過程でのメモから回収する。ただし、今の持っている長さの方が、逆算過程からの要求長さより長いならそのままキープ。

1ケースだけWAになってしまったが、上をうまく実装できてない可能性もある。ともかく、3ケースだけTLEで落ちる。

GitHubと似ている。

struct Node {
    int val, parent;
    vector<int> next_idx;
    Node(int a, int b) { val = a, parent = b; }
};

こんな風にNodeを作って、vectorにでも入れて、木を作る。そして、注目してるノード(のvectorのなかでのindex)をカーソルとする。

まずは、Node(-1, -1)で根のノードを作り、カーソルをそこに置く。次のように操作する。

ADD　今のカーソルの子に新しいノードを作り、カーソルをそこに置く。
- この時、子にvalが同じなノードがあったとしても、別の新しいノードを作る。その判定をすること自体が線形時間かかってしまうからである。今回の制約では全部新しく作ってもメモリ的には超過とはならない。
DELETE　今のカーソルを親に置く。もう親がないのならば、それは空列なのでカーソルそのまま。
SAVE X std::map<int, int> reference;のように作り、reference[X] = カーソル;として、連想配列で保存。
LOAD X カーソル = reference[X];

ここで、連想配列を使用することによって全体では$ O(Q \log Q) $時間がかかる。ここでは、SAVEとLOADは、木構造で列を保持する事によって、どの頂点かを保持するだけで一意に全ての操作に$ O(1) $で対応できるのがポイント。

このように、スタックの操作を撒き戻したりすることはまさにGitHubのツリーの形そのものである、言われてみればそう。

noshiさんの解説。私も家に永続データ構造飾ります。

今回の要求されるのはスタックというデータ構造であるが、これを永続化させたもの。永続化データ構造とは、

普通のそのデータ構造の動きができる。
過去のある時点でのデータ構造のデータを、低コストで保持できる。
- 例えば、std::stackはコピーしておくと、入れたデータのサイズ$ n $に依存した時間$ O(n) $かかってしまう。

今回の場合、うまく木で実装したことによって、複数回stack自体を保存する前提で、1回ごとの操作量に均したとき、操作を終えたあとのstack自体を保存させるには、本質的にはノード1つぶんとそれを指し示すindexだけである。これはほぼ$ O(1) $に近い。

上のように、木で実装したのが永続スタック。

永続データ構造を一通り勉強して家に飾ろう。