Day 026-Q3 — オンライン凸包トリック (Li Chao Tree)

2026-05-09 赤色 Master / Phase 8+ ★★★★★★★★★ Li Chao Tree / CHT

問題

直線 $y = ax + b$ の追加と、点 $x$ での最小値クエリをオンラインに処理する。

制約

$1 \le N \le 2 \times 10^5$
$-10^9 \le a, b, x \le 10^9$

入出力例

入力例 1

7
ADD 1 3
ADD -1 5
QUERY 0
ADD 2 -1
QUERY 1
QUERY 3
ADD 0 2
QUERY 2

出力例 1

3
1
...
...

ヒント (段階的開示)

ヒント1: 方向性
Li Chao Tree: $x$ 値域を管理する動的セグ木。各ノードは中点で最良の直線を保持。
ヒント2: アプローチ
追加時は中点で比較、劣る直線を子へ再帰。クエリはルート〜葉を辿り最小値を取る。$O(\log V)$。
ヒント3: 誘導
動的ノード生成で空間 $O(N \log V)$。

模範解答 (Python)

import sys
input = sys.stdin.readline
INF = float('inf')

class LiChaoNode:
    __slots__ = ['line', 'left', 'right']
    def __init__(self):
        self.line = None
        self.left = None
        self.right = None

class LiChaoTree:
    def __init__(self, lo, hi):
        self.lo = lo; self.hi = hi
        self.root = LiChaoNode()
    def _val(self, line, x):
        if line is None: return INF
        return line[0] * x + line[1]
    def add(self, line):
        self._add(self.root, line, self.lo, self.hi)
    def _add(self, node, line, lo, hi):
        mid = (lo + hi) // 2
        left_better = self._val(line, lo) < self._val(node.line, lo)
        mid_better = self._val(line, mid) < self._val(node.line, mid)
        if mid_better:
            node.line, line = line, node.line
        if lo == hi: return
        if left_better != mid_better:
            if node.left is None: node.left = LiChaoNode()
            self._add(node.left, line, lo, mid)
        else:
            if node.right is None: node.right = LiChaoNode()
            self._add(node.right, line, mid + 1, hi)
    def query(self, x):
        return self._query(self.root, x, self.lo, self.hi)
    def _query(self, node, x, lo, hi):
        if node is None: return INF
        res = self._val(node.line, x)
        if lo == hi: return res
        mid = (lo + hi) // 2
        if x <= mid: return min(res, self._query(node.left, x, lo, mid))
        else: return min(res, self._query(node.right, x, mid + 1, hi))

def solve():
    N = int(input())
    LO, HI = -10**9, 10**9
    tree = LiChaoTree(LO, HI)
    out = []
    for _ in range(N):
        ops = input().split()
        if ops[0] == "ADD":
            tree.add((int(ops[1]), int(ops[2])))
        else:
            x = int(ops[1])
            ans = tree.query(x)
            out.append(str(ans if ans < INF else 0))
    print('\n'.join(out))

solve()

Step-by-Step 解説

1Li Chao Tree
各ノードに中点で最良の直線を保持。中点が「最良」とは $x = mid$ で最小。
2追加
中点比較で入れ替え。left_better != mid_better → 左に再帰、それ以外は右。
3クエリ
ルート〜葉まで辿り、各ノードでの値を min。$O(\log V)$。
4動的ノード
必要なノードのみ生成。空間 $O(N \log V)$。

よくあるミス

ミス原因正しい書き方
None 直線の値None チェック忘れ_val で INF を返す
mid の丸め(lo+hi)//2 負方向切り捨て方向に注意
最大値クエリ符号反転忘れ$(-a, -b)$ で追加し結果を負化

次のステップ

  • 傾き単調 deque CHT (O(N))
  • 動的 vs Li Chao の速度比較

自己評価

自分の回答

気づき・メモ