Day 075-Q5 — オンライン動的凸包・Li Chao Tree（直線追加・最大値クエリ O(Q log C)）

問題

$Q$ 個のオンラインクエリを処理せよ（前クエリの出力に依存する XOR エンコードあり）。

• クエリ 1 a b: 直線 $y = ax + b$ を追加する（XOR デコード後の値）
• クエリ 2 x: 現在追加されている全直線の中で $x$ を代入したときの最大値を出力

XOR エンコード: パラメータに直前の 2 クエリの答え $\text{last}$ を XOR してデコードする（初期値 $\text{last} = 0$）。

入出力例

4
1 2 3
1 -1 10
2 4
2 0

11
10

直線 $y=2x+3$ と $y=-x+10$。$x=4$: $\max(11, 6)=11$。$x=0$: $\max(3,10)=10$。

概念図: Li Chao Tree の直線管理

ヒント

class LiChaoTree:
    def __init__(self, lo, hi):
        self.lo = lo; self.hi = hi
        self.line = None  # (a, b) または None
        self.left = self.right = None

    def add(self, a, b):
        mid = (self.lo + self.hi) >> 1
        if self.line is None:
            self.line = (a, b); return
        la, lb = self.line
        better_mid = (a * mid + b) > (la * mid + lb)
        if better_mid:
            self.line, a, b = (a, b), la, lb
        if self.lo == self.hi: return
        better_left = (a * self.lo + b) > (la * self.lo + lb)
        if better_left != better_mid:  # 左に再帰
            if self.left is None: self.left = LiChaoTree(self.lo, mid)
            self.left.add(a, b)
        else:  # 右に再帰
            if self.right is None: self.right = LiChaoTree(mid+1, self.hi)
            self.right.add(a, b)

模範解答

import sys
input = sys.stdin.readline

class LiChaoTree:
    def __init__(self, lo, hi):
        self.lo = lo; self.hi = hi
        self.line = None; self.left = self.right = None

    def add(self, a, b):
        mid = (self.lo + self.hi) >> 1
        if self.line is None: self.line = (a, b); return
        la, lb = self.line
        better_left = (a*self.lo+b) > (la*self.lo+lb)
        better_mid  = (a*mid+b)    > (la*mid+lb)
        if better_mid:
            self.line, a, b = (a, b), la, lb; la, lb = self.line
        if self.lo == self.hi: return
        if better_left != better_mid:
            if self.left is None: self.left = LiChaoTree(self.lo, mid)
            self.left.add(a, b)
        else:
            if self.right is None: self.right = LiChaoTree(mid+1, self.hi)
            self.right.add(a, b)

    def query(self, x):
        res = -float('inf')
        if self.line is not None: res = self.line[0]*x + self.line[1]
        if self.lo == self.hi: return res
        mid = (self.lo + self.hi) >> 1
        if x <= mid:
            if self.left is not None: res = max(res, self.left.query(x))
        else:
            if self.right is not None: res = max(res, self.right.query(x))
        return res

def solve():
    Q = int(input())
    COORD = 2 * 10**9
    tree = LiChaoTree(-COORD, COORD)
    last = 0; out = []
    for _ in range(Q):
        parts = list(map(int, input().split()))
        t = parts[0]
        if t == 1:
            a = parts[1] ^ last; b = parts[2] ^ last
            tree.add(a, b)
        else:
            x = parts[1] ^ last
            ans = tree.query(x); last = ans; out.append(ans)
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: Li Chao Tree の本質

座標軸 $[-C, C]$ を再帰的に2分割するセグメント木。各ノードは「その担当区間の中点 $\text{mid}$ で最も大きい直線」を保持する。追加時に中点で比較し、負けた方を子へ送ることで、各直線は高々 $O(\log C)$ ノードにしか訪問しない。

Step 2: 追加の正確な処理

ノードに直線 $(la, lb)$ が格納されている状態で新直線 $(a, b)$ を追加する場合:

1. 中点 $\text{mid}$ での値が大きい方（勝者）をノードに格納
2. 敗者を「左端での比較」と「中点での比較」の一致/不一致で左右の子に振り分ける

なぜこれで正しいか: 勝者が負けうる領域（交点の反対側）に敗者を送るため、包絡線の形状が保たれる。

Step 3: クエリ

$x$ でのクエリはルートから葉方向へ辿り、通過する全ノードの直線を評価して最大値を返す。$x \le \text{mid}$ なら左子、$x > \text{mid}$ なら右子へ進む。計算量 $O(\log C)$。

Step 4: オンライン XOR エンコード

前クエリの答え last を XOR することで、後続クエリが前の答えに依存する。オフライン前処理（全クエリ既知）が使えないことを強制するテクニック。Li Chao Tree はオンラインなので直接対応できる。

よくあるミス

次のステップ

• 発展問題: Li Chao Tree で最小値クエリ（下包絡線）・Convex Hull Trick（$x$ 単調時の $O(1)$ クエリ）との比較と使い分け

自己評価