Day 142-Q3 | Banker's Queue

問題

FIFOキューに対する$M$個の操作が与えられる。各操作は既存のバージョン番号を参照し、新しいバージョンを1つ作る。バージョン$0$は空のキューを表す。

1 v x: バージョン$v$のキューの末尾に値$x$を追加した新しいキューを作る（新バージョン番号はこの操作の番号）
2 v: バージョン$v$のキューの先頭を取り除いた新しいキューを作り、取り除いた値を出力する

過去のどのバージョンも、その後の操作によって内容が変化しない（永続データ構造）。同じバージョンを複数の操作が参照して枝分かれすることもある。

Okasaki の Banker's Queue（前半を遅延ストリーム、後半を不変連結リストとして持ち、後半が前半より長くなったら回転を遅延させて仕込む手法）に基づいて実装し、各2 v操作の取り除いた値を出力せよ。

入力形式

M
op_1
:
op_M

制約

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

1 v xの$v$は$0\le v<i$を満たす既存バージョン

2 vの$v$は空でないキューを指す

$0 \le x \le 10^9$

入出力例

入力例1

出力例1

1
1
2

概念図

ヒント（段階的開示）

ヒント1（方向性）

「前半配列＋後半配列、後半が長くなったらreverseして付け替える」実装は償却$O(1)$になるが、これは同じキューに操作を繰り返す前提の分析。永続データ構造として過去バージョンに何度も分岐すると、償却の前提が崩れ同じ高コストなreverseを何度も引き起こされる。

ヒント2（アプローチ）

reverseという重い処理を一度に全部やらず遅延評価で少しずつ実行する。前半を遅延ストリームとして持ち、popのたびに次の要素を1つだけ強制評価する。回転が必要になった瞬間、その処理全体を「まだ実行されていない計算」として仕込み、その後の各popでごく一部だけが評価される。結果はメモ化されるため同じバージョンに何度分岐しても再計算されない。

ヒント3（誘導）

class SCons:
    __slots__ = ("head", "_thunk", "_val", "_forced")
    def __init__(self, head, thunk):
        self.head = head
        self._thunk = thunk
        self._val = None
        self._forced = False
    def tail(self):
        if not self._forced:
            self._val = self._thunk()
            self._forced = True
        return self._val

def rotate(f, r, a):
    # 不変条件: len(r) == len(f) + 1
    if f is None:
        return SCons(r.head, lambda: a)
    else:
        return SCons(f.head, lambda: rotate(f.tail(), r.tail, SCons(r.head, lambda: a)))

模範解答 (Python)

import sys

class LNil:
    pass
LNIL = LNil()

class LNode:
    __slots__ = ("head", "tail")
    def __init__(self, head, tail):
        self.head, self.tail = head, tail

def lcons(x, lst):
    return LNode(x, lst)

class SNil:
    pass
SNIL = SNil()

class SCons:
    __slots__ = ("head", "_thunk", "_val", "_forced")
    def __init__(self, head, thunk):
        self.head = head
        self._thunk = thunk
        self._val = None
        self._forced = False
    def tail(self):
        if not self._forced:
            self._val = self._thunk()
            self._forced = True
            self._thunk = None
        return self._val

def s_empty(s):
    return isinstance(s, SNil)

def rotate(f, r, a):
    if s_empty(f):
        return SCons(r.head, lambda: a)
    else:
        return SCons(f.head, lambda: rotate(f.tail(), r.tail, SCons(r.head, lambda: a)))

class BQueue:
    __slots__ = ("f", "lf", "r", "lr")
    def __init__(self, f, lf, r, lr):
        self.f, self.lf, self.r, self.lr = f, lf, r, lr

EMPTY = BQueue(SNIL, 0, LNIL, 0)

def check(f, lf, r, lr):
    if lr <= lf:
        return BQueue(f, lf, r, lr)
    else:
        newf = rotate(f, r, SNIL)
        return BQueue(newf, lf + lr, LNIL, 0)

def push(q, x):
    return check(q.f, q.lf, lcons(x, q.r), q.lr + 1)

def pop(q):
    x = q.f.head
    newf = q.f.tail()
    return x, check(newf, q.lf - 1, q.r, q.lr)

def main():
    data = sys.stdin.read().split("\n")
    m = int(data[0])
    versions = {0: EMPTY}
    out = []
    for i in range(1, m + 1):
        parts = data[i].split()
        if parts[0] == "1":
            v, x = int(parts[1]), int(parts[2])
            versions[i] = push(versions[v], x)
        else:
            v = int(parts[1])
            val, versions[i] = pop(versions[v])
            out.append(str(val))
    print("\n".join(out))

main()

Step-by-Step 解説

1単純2リストキューが永続化で壊れる理由
reverse直後の状態から何度も分岐してpopを繰り返すと、その都度reverseが必要なバージョンを作り出せてしまい全体でO(N²)になりうる。

2遅延評価による解決
rotateをSConsのtailにlambdaで包み未評価にしておく。popのたびにtail()を1回呼ぶことで巨大な計算が1ステップずつしか進まない。メモ化されるため再計算もされない。

3分岐しても壊れない理由
各SCons/LNodeはイミュータブルで複数バージョンから安全に共有される。tail()のメモ化は各ノード自身に閉じているため他バージョンに影響しない。

4不変条件 lr ≤ lf
この不変条件があるからこそrotateが呼ばれる時点で「後半の要素数 = 前半の要素数+1」というバランスが保証される。

5計算量
pushはO(1)。popはtail()を1回呼ぶだけで実質O(1)（メモ化によりrotateの1ステップ分のみ発生）。全体でO(M)。

よくあるミス

ミス	原因	正しい書き方
tail()の結果をメモ化せず毎回_thunk()を呼び直す	遅延評価と毎回再計算する遅延実行を混同している	_forced/_valでメモ化し2回目以降は保存済みの値を返す
後半リストをPythonのlistで実装してしまう	可変なリストは複数バージョンで安全に共有できない	後半もLNodeによるイミュータブルな連結リストにする
不変条件判定をlr<lfやlr<=lf+1にしてしまう	前半・後半の許容比のバランス条件を誤解している	lr<=lfを境界としそれを超えたときのみ回転する
空のキューからpopしようとして例外になる	バージョンが空かどうかのチェックを怠っている	lf==0のときpop不可として扱う（本問は入力保証あり）
バージョン管理を1つの変数で使い回し過去バージョンを上書きしてしまう	永続性の要件を見落としている	versions[i]のように各バージョンを個別に保存する

次のステップ

発展: pushを先頭にもpopを末尾にも行える両端キューへ拡張せよ（Hood-Melvilleのリアルタイムデックはさらに複雑な段階的回転管理が必要）。
発展2: 分岐なしで実行した場合と意図的に大量分岐させた場合とで実行時間を比較し、分岐の有無が実行時間に影響しないこと（真の永続性）を実測で確認せよ。

自己評価

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

Day 142-Q3 — Banker's Queue（Okasaki永続実時間キュー）

問題