動的中央値クエリ
(DataStructure/misc/DynamicMedian.py)

• View this file on GitHub
• Last update: 2022-01-22 18:47:07+09:00

概要

DynamicMedian: 集合の中央値を動的に管理するデータ構造

使い方

DynamicMedian()
中央値を管理する空の集合を構築する。計算量 $O(1)$

• add(val: int) -> None
  集合に要素 val を追加する。集合の大きさを n とすると、計算量 $O(\log n)$

• median_low() -> int
  集合の中央値を返す。ただし、集合の大きさが偶数の場合は中央の2値の小さい方を返す。計算量 $O(1)$

• median_low() -> int
  集合の中央値を返す。ただし、集合の大きさが偶数の場合は中央の2値の大きい方を返す。計算量 $O(1)$

• minimum_query() -> int
  集合を ${a_1, a_2, \dots, a_n }$ としたときの $\min(|x - a_1| + |x - a_2| + ⋯ + |x - a_n|)$ を返す。$x$ は集合の中央値となる。計算量 $O(1)$

Verified with

• TestCase/AtCoder/abc127_f.test.py

Code

# from heapq import heappushpop, heappush
from standard_library.heapq import heappushpop, heappush


class DynamicMedian:
    def __init__(self):
        self.l_q = []
        self.r_q = []
        self.l_sum = 0
        self.r_sum = 0

    def add(self, val):
        if len(self.l_q) == len(self.r_q):
            self.l_sum += val
            val = -heappushpop(self.l_q, -val)
            self.l_sum -= val
            heappush(self.r_q, val)
            self.r_sum += val
        else:
            self.r_sum += val
            val = heappushpop(self.r_q, val)
            self.r_sum -= val
            heappush(self.l_q, -val)
            self.l_sum += val

    def median_low(self):
        if len(self.l_q) + 1 == len(self.r_q):
            return self.r_q[0]
        else:
            return -self.l_q[0]

    def median_high(self):
        return self.r_q[0]

    def minimum_query(self):
        """min(|x - a_1| + |x - a_2| + ⋯ + |x - a_N|) s.t. any x"""
        res1 = (len(self.l_q) * self.median_high() - self.l_sum)
        res2 = (self.r_sum - len(self.r_q) * self.median_high())
        return res1 + res2

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