Foldable Queue
(DataStructure/misc/FoldableQueue.py)

• View this file on GitHub
• Last update: 2022-09-12 02:00:29+09:00

概要

キューの操作をサポートし、キュー全体の畳み込みを $O(1)$ で行えるデータ構造。畳み込みは半群を要請する。

使い方

SlidingWindowAggregation(op: Callable[[Any, Any], Any])
空のキューを構築する。op は畳み込みの二項演算。計算量 $O(1)$

• __len__() -> int
  キューの大きさを返す。計算量 $O(1)$

• all_fold() -> Any
  キュー全体の畳み込み結果を返す。計算量 $O(1)$

• append(val: Any) -> None
  キューの末尾に要素 val を追加する。計算量 $O(1)$

• popleft() -> Any
  キューの先頭要素を削除し、その要素を返す。計算量 $\mathrm{amortized}\ O(1)$

Verified with

• TestCase/AOJ/DSL_3_A.test.py
• TestCase/AOJ/DSL_3_D.test.py
• TestCase/LibraryChecker/queue_operate_all_composite.test.py

Code

class FoldableQueue:
    def __init__(self, op):
        self.op = op
        self.inque = []
        self.outque = []

    def __len__(self):
        return len(self.outque) + len(self.inque)

    def _trans(self):
        val, _ = self.inque.pop()
        self.outque.append((val, val))
        acc = val
        while self.inque:
            val, _ = self.inque.pop()
            acc = self.op(val, acc)
            self.outque.append((val, acc))

    def all_fold(self):
        if not self.inque:
            return self.outque[-1][1]
        if not self.outque:
            return self.inque[-1][1]
        return self.op(self.outque[-1][1], self.inque[-1][1])

    def append(self, val):
        if self.inque:
            self.inque.append((val, self.op(self.inque[-1][1], val)))
        else:
            self.inque.append((val, val))

    def popleft(self):
        if not self.outque:
            self._trans()
        val = self.outque.pop()
        return val[0]

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page