Li-Chao Tree
(DataStructure/SegmentTree/LiChaoTree.py)

• View this file on GitHub
• Last update: 2021-01-03 06:18:12+09:00

使い方

LiChaoTree(xs: Iterable[int], INF=10**18)
xs の要素を min クエリにおける $x$ 座標として使用可能な、空の直線 (線分) 集合を構築する。計算量 $O(n \log n)$

• add_line(line: Tuple[int, int]) -> None
  集合に (傾き, 切片) で表される直線 line を追加する。計算量 $O(\log n)$

• add_seg(line: Tuple[int, int], l: int, r: int) -> None
  集合に (傾き, 切片) で表される線分 line (ただし $x \in [l,r)$) を追加する。計算量 $O(\log ^2 n)$

• min(x: int) -> int
  $x$ 座標が x のときの、$y$ 座標の最小値を返す。そのような $y$ 座標が存在しない場合は INF を返す。x が xs の要素でない場合は例外 KeyError が発生するので注意。計算量 $O(\log n)$

Verified with

• TestCase/LibraryChecker/line_add_get_min.test.py
• TestCase/LibraryChecker/segment_add_get_min.test.py

Code

from bisect import bisect_left


class LiChaoTree:
    def __init__(self, xs, INF=10**18):
        self.INF = INF
        xs = sorted(list(set(xs)))
        n = len(xs)
        self.size = 1 << (n - 1).bit_length()
        self.comp_xs = {x: ind for ind, x in enumerate(xs)}
        self.xs = xs + [self.INF] * (self.size - n)
        self.data = [None] * (self.size + self.size)

    def update(self, line, k, l, r):
        while True:
            if self.data[k] is None:
                self.data[k] = line
                return
            mid = (l + r) >> 1
            lx, mx, rx = self.xs[l], self.xs[mid], self.xs[r - 1]
            lu = self.f(line, lx) < self.f(self.data[k], lx)
            mu = self.f(line, mx) < self.f(self.data[k], mx)
            ru = self.f(line, rx) < self.f(self.data[k], rx)
            if lu and ru:
                self.data[k] = line
                return
            if not lu and not ru:
                return
            if mu:
                self.data[k], line = line, self.data[k]
            if lu != mu:
                r, k = mid, k << 1
            else:
                l, k = mid, k << 1 | 1

    def add_line(self, line):
        self.update(line, 1, 0, self.size)

    def add_seg(self, line, l, r):
        l = bisect_left(self.xs, l)
        r = bisect_left(self.xs, r)
        l0, r0 = l + self.size, r + self.size
        size = 1
        while l0 < r0:
            if l0 & 1:
                self.update(line, l0, l, l + size)
                l0 += 1
                l += size
            if r0 & 1:
                r0 -= 1
                r -= size
                self.update(line, r0, r, r + size)
            l0 >>= 1
            r0 >>= 1
            size <<= 1

    def f(self, line, x):
        a, b = line
        return a * x + b

    def min(self, x):
        k = self.comp_xs[x] + self.size
        res = self.INF
        while k > 0:
            if self.data[k] is not None:
                res = min(res, self.f(self.data[k], x))
            k >>= 1
        return res

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