SWAG
(expansion/data_structure/SWAG.py)

• View this file on GitHub
• Last update: 2023-06-21 23:36:41+09:00

概要

deque に対して要素の追加 / 削除 / 現在の列に対する演算結果取得 を処理します．

演算については

• $f(a, f(b, c)) = f(f(a, b), c)$
• 単位元が存在する

ものを想定しています．（本当は単位元はいらないはずなんですが，実装の都合上要求しているので，ない場合は適当に取りえない値を設定して演算の中で if 文を入れてください）

使い方

• __init__(ope, e) := 扱う演算を定義します
• push(x) := deque の末尾に x を追加します．
• pop(x) := deque の先頭の要素を削除します．
• prod() := 現在の deque 列に対する演算結果を返します
• size() := deque 列の長さを返します．
• __len__ := 上記同様
• clear() := deque を空にします．

Code

class SWAG:
    def __init__(self, ope, e):
        self.L = []
        self.R = []
        self.Lcum = [e]
        self.Rall = e
        self.ope = ope
        self.e = e

    def push(self, x):
        self.R.append(x)
        self.Rall = self.ope(self.Rall, x)

    def pop(self):
        if not self.L:
            while self.R:
                self.L.append(self.R.pop())
                self.Lcum.append(self.ope(self.L[-1], self.Lcum[-1]))
            self.Rall = self.e
        self.L.pop()
        self.Lcum.pop()

    def prod(self):
        return self.ope(self.Lcum[-1], self.Rall)

    def size(self):
        return len(self.L) + len(self.R)

    def __len__(self):
        return self.size()

    def clear(self):
        self.L = []
        self.R = []
        self.Lcum = [self.e]
        self.Rall = self.e

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page