Day 009-Q2 — Li Chao Tree（直線の最小値クエリ）

2026-04-22 黄色 / Phase 6 ★★★★★★ Li Chao Tree

問題

$Q$ 個のクエリを処理せよ。

  • add a b : 直線 $y = ax + b$ を追加
  • query x : 現在の全直線の中で $x$ における $y$ の最小値を答える

制約

$1 \le Q \le 2 \times 10^5$
$-10^9 \le a, b \le 10^9$
$0 \le x \le 10^6$

入出力例

入力例 1

5
add 1 0
add -1 6
query 2
query 4
query 3

出力例 1

2
2
3

ヒント (段階的開示)

ヒント1: 方向性
愚直は $O(QN)$。Li Chao Tree（セグメント木の変形）で $O(\log X)$。
ヒント2: アプローチ
$x$ の定義域をセグメント木の区間として管理し、各ノードに「その区間の中点で最小値を与える直線」を記録。
ヒント3: 誘導
add: 中点で勝る直線をノードに置き、負けた直線を子に伝播。query: ルートから x を含む区間を辿り最小値を返す。

模範解答 (Python)

import sys
input = sys.stdin.readline

INF = float('inf')
X_MAX = 10**6

class LiChaoTree:
    def __init__(self, lo, hi):
        self.lo = lo
        self.hi = hi
        self.size = hi - lo + 1
        self.seg = [None] * (4 * self.size)

    def _add(self, node, lo, hi, line):
        if lo > hi:
            return
        mid = (lo + hi) // 2
        a, b = line
        if self.seg[node] is None:
            self.seg[node] = line
            return
        la, lb = self.seg[node]
        left_better  = a * lo  + b < la * lo  + lb
        mid_better   = a * mid + b < la * mid + lb
        if mid_better:
            self.seg[node], line = line, self.seg[node]
            a, b = self.seg[node]
            la, lb = line
            left_better = not left_better
        if lo == hi:
            return
        if left_better:
            self._add(2 * node, lo, mid, (la, lb))
        else:
            self._add(2 * node + 1, mid + 1, hi, (la, lb))

    def add(self, a, b):
        self._add(1, self.lo, self.hi, (a, b))

    def _query(self, node, lo, hi, x):
        if self.seg[node] is None:
            return INF
        a, b = self.seg[node]
        res = a * x + b
        if lo == hi:
            return res
        mid = (lo + hi) // 2
        if x <= mid:
            return min(res, self._query(2 * node, lo, mid, x))
        else:
            return min(res, self._query(2 * node + 1, mid + 1, hi, x))

    def query(self, x):
        return self._query(1, self.lo, self.hi, x)

def solve():
    Q = int(input())
    lct = LiChaoTree(0, X_MAX)
    out = []
    for _ in range(Q):
        cmd = input().split()
        if cmd[0] == 'add':
            a, b = int(cmd[1]), int(cmd[2])
            lct.add(a, b)
        else:
            x = int(cmd[1])
            out.append(lct.query(x))
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

1Li Chao Tree の概要
セグメント木の各ノードに「支配的な直線」を格納。
2add 操作
中点で勝った直線をノードに置き、負けた直線を子へ降ろす。
3query 操作
ルートから x を含む区間を辿り、各ノードの直線を評価。

よくあるミス

ミス原因正しい書き方
add 後に left_better 再評価しない直線交換後は判定が逆転left_better = not left_better
x の範囲外でアクセスクランプを忘れる制約内の x のみ扱う
INF を小さく設定係数大でオーバーフローfloat('inf')

次のステップ

  • 発展問題: $x$ の範囲が負を含む場合（座標圧縮）
  • CHT（Convex Hull Trick）との比較

自己評価

自分の回答

気づき・メモ