Day 138-Q4 | 永続スタック（Persistent Stack）

問題

スタックに対して以下の3種類のクエリを $Q$ 個、順番に処理せよ。このスタックは永続的であり、過去のどのバージョンに対しても操作を行うことができ、操作しても過去のバージョンは変化しない。

バージョン $0$ は「空のスタック」として最初から存在する。クエリ1・2が実行されるたびに新しいバージョン番号（それまでに実行された1・2クエリの累計回数）が生成される。

1 t x : バージョン $t$ のスタックに $x$ を push した新しいスタックを作り、新バージョンとする。
2 t : バージョン $t$ のスタックから1つ pop した新しいスタックを作り、新バージョンとする（$t$ が空でないことが保証される）。
3 t : バージョン $t$ の一番上の値を出力する。空なら -1。新バージョンは生成しない。

$t$ には、それ以前に生成された任意のバージョン番号を指定でき、同じバージョンから複数回分岐することもある。全クエリを合計 $O(Q)$（1クエリあたり $O(1)$）で処理せよ。

入力形式

Q
query_1
...
query_Q

制約

$1 \le Q \le 2\times10^5$

$0 \le x \le 10^9$

$t$ は既存の生成済バージョン番号

クエリ2の$t$は空でないことが保証

入出力例

入力例1

出力例1

3
5
-1

入力例2

出力例2

10
20

概念図

ヒント（段階的開示）

ヒント1（方向性）

普通のスタックを配列やlistで実装すると、push/popのたびに書き換わるため過去のバージョンに戻れない。まるごとコピーすれば実現できるが$O(N)$かかる。スタックは実は「一番上の要素」＋「それより下の部分（＝もう1つのスタック）」という再帰的な構造になっていることに気づけないか。

ヒント2（アプローチ）

スタックを「値」と「1つ下のスタックへのポインタ」を持つイミュータブルな単方向リンクリストのノードとして表現する。pushは新しいノードを1つ作り、それが指す先を元のスタックの先頭ノードにするだけ。popはそのノードが指す次のノードを新しい先頭とするだけ。どちらも元のノードは一切変更しないので過去のバージョンはそのまま残る。

ヒント3（誘導）

val = [0]          # val[i]: ノードiの値
nxt = [0]          # nxt[i]: ノードiの1つ下のノード(0なら空)
version_top = [0]  # version_top[v]: バージョンvの先頭ノード

def push(t, x):
    val.append(x)
    nxt.append(version_top[t])
    version_top.append(len(val) - 1)

def pop(t):
    top = version_top[t]
    version_top.append(nxt[top])

def query_top(t):
    top = version_top[t]
    return -1 if top == 0 else val[top]

push・popそれぞれで新バージョン番号が1つ増える(version_topに1要素追加するたびに進む)ことに注意。

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    Q = int(data[idx]); idx += 1

    # ノード0は空スタックを表す番兵
    val = [0]
    nxt = [0]
    version_top = [0]  # version_top[0] = 0 (空スタック)

    out = []
    for _ in range(Q):
        typ = data[idx]; idx += 1
        if typ == b'1':
            t = int(data[idx]); idx += 1
            x = int(data[idx]); idx += 1
            val.append(x)
            nxt.append(version_top[t])
            version_top.append(len(val) - 1)
        elif typ == b'2':
            t = int(data[idx]); idx += 1
            top = version_top[t]
            version_top.append(nxt[top])
        else:
            t = int(data[idx]); idx += 1
            top = version_top[t]
            out.append("-1" if top == 0 else str(val[top]))

    print("\n".join(out))


main()

Step-by-Step 解説

1スタックをノードの連結として捉える
スタック[5,3](3が一番上)は「値3のノード」→「値5のノード」→「空」という連結リストと同一視できる。先頭ノード1つを指せばスタック全体を表現できる。

2pushは新ノード1個の追加だけ
push(t,x)は値xを持つ新しいノードを作りnxtをバージョンtの先頭にするだけ。元のバージョンtが指していたノード列は無変更のまま残る。

3popは「1つ下を新しい先頭にする」だけ
pop(t)は新しいノードすら作らず、バージョンtの先頭ノードのnxtを新バージョンの先頭として登録するだけ。

4バージョン管理配列version_top
各バージョン番号vに「そのバージョンの先頭ノード番号」を記録した配列を用意し、push・popのたびに1要素追加することで新バージョンが生成される。

5過去バージョンが保存される理由
ノードは一度作られたら書き換えられない(イミュータブル)。バージョンは「どのノードを先頭とみなすか」というポインタの違いでしかなく、複数バージョンが同じノード列の一部を共有できる。

よくあるミス

ミス	原因	正しい書き方
pushのたびにスタック全体をコピーする	永続化を「毎回複製」と誤解する	新ノード1つを作り下位ノードへのポインタを繋ぐだけにする(共有を活かす)
ノード番号とバージョン番号を混同する	両方とも増えていく整数なので取り違えやすい	ノード(val/nxt)とバージョン(version_top)は別のインデックス空間として管理する
pop時に新ノードを作ってしまう	pushと同じ処理だと勘違いする	popは既存のノード(1つ下)を指すだけで新規ノードは不要
バージョン0(空)のnxt参照でエラー	番兵ノード0のnxt[0]が未定義だと誤解する	ノード0はval[0]=0,nxt[0]=0の番兵として初期化しておく
クエリ3もバージョンを消費すると誤解する	クエリ番号とバージョン番号の対応を混同	クエリ3は新バージョンを生成しない。バージョン番号はクエリ1・2の累計実行回数と一致

次のステップ

発展: 同様の考え方で「永続キュー」(2本のスタックによる実装、または永続片方向リストの工夫)を実装せよ。スタックほど自明ではない点に注意。
発展2: 「バージョン$t_1$と$t_2$の共通する末尾部分(いつ分岐したか)」を求めるクエリを追加し、各ノードに深さ情報を付与しLCA的に求める方法を検討せよ。

自己評価

完全理解おおむね理解要復習

Day 138-Q4 — 永続スタック（Persistent Stack）

問題