Day 045-Q3 | オンライン動的凸包（Li Chao Tree）

問題

$Q$ 個のオンラインクエリを処理せよ：

+ a b：直線 $y = ax + b$ を集合に追加する
? x：現在の全直線での $x$ における最大値を求める（実際の $x$ は x XOR last_ans）

$last\_ans$ は直前の ? クエリの答え（最初は 0）。

制約

$1 \le Q \le 2 \times 10^5$

$|a|, |b| \le 10^9$

$|x| \le 10^{18}$（復元後）

クエリ ? は少なくとも1回出現

時間制限: 2秒

入出力例

入力例 1

6
+ 1 0
+ -1 4
? 2
+ 0 5
? 3
? 0

出力例 1

2
5
5

概念図: Li Chao Tree の直線挿入

ヒント（段階的開示）

ヒント1: 方向性

オフラインであれば座標圧縮した Li Chao Tree や CHT が使えますが、オンライン（XOR 暗号化）の場合は値域 $[-2 \times 10^{18}, 2 \times 10^{18}]$ を動的に管理する Li Chao Tree が有効です。

ヒント2: アプローチ

Li Chao Tree は各ノードが「その区間の中点で最大の直線」を1本保持
動的ノード生成で $[-2 \times 10^{18}, 2 \times 10^{18}]$ を扱う
追加: $O(\log(\text{値域}))$、クエリ: $O(\log(\text{値域}))$

ヒント3: 実装骨格

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

def add(node, lo, hi, a, b):
    mid = (lo + hi) >> 1
    if node.line is None:
        node.line = (a, b); return
    ca, cb = node.line
    mid_new = a*mid+b > ca*mid+cb
    if mid_new: node.line, (a,b) = (a,b), (ca,cb)
    if lo == hi: return
    left_new = a*lo+b > ca*lo+cb
    if left_new != mid_new:
        if not node.left: node.left = LiChaoNode()
        add(node.left, lo, mid, a, b)
    else:
        if not node.right: node.right = LiChaoNode()
        add(node.right, mid+1, hi, a, b)

模範解答 (Python)

import sys
input = sys.stdin.readline

INF = 2 * 10**18

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 _add(self, node, lo, hi, a, b):
        mid = (lo + hi) >> 1
        if node.line is None:
            node.line = (a, b)
            return
        ca, cb = node.line
        left_new = a * lo + b > ca * lo + cb
        mid_new = a * mid + b > ca * mid + cb
        if mid_new:
            node.line = (a, b)
            a, b = ca, cb
        if lo == hi:
            return
        if left_new != mid_new:
            if node.left is None:
                node.left = LiChaoNode()
            self._add(node.left, lo, mid, a, b)
        else:
            if node.right is None:
                node.right = LiChaoNode()
            self._add(node.right, mid + 1, hi, a, b)

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

    def _query(self, node, lo, hi, x):
        if node is None:
            return -INF
        res = -INF
        if node.line is not None:
            a, b = node.line
            res = a * x + b
        mid = (lo + hi) >> 1
        if x <= mid:
            res = max(res, self._query(node.left, lo, mid, x))
        else:
            res = max(res, self._query(node.right, mid + 1, hi, x))
        return res

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

def main():
    Q = int(input())
    tree = LiChaoTree(-INF, INF)
    last_ans = 0
    results = []
    for _ in range(Q):
        line = input().split()
        if line[0] == '+':
            a, b = int(line[1]), int(line[2])
            tree.add(a, b)
        else:
            x = int(line[1]) ^ last_ans
            ans = tree.query(x)
            last_ans = ans
            results.append(ans)
    print('\n'.join(map(str, results)))

main()

Step-by-Step 解説

1Li Chao Tree の基本
区間 $[l, r]$ を管理するセグメント木。各ノードは「その区間の中点で最大となる直線」を1本保持する。

2直線追加 $O(\log(\text{値域}))$
中点でノードの直線と比較し、優れた方をノードに格納。負けた直線を左右の子に再帰的に押し込む。最大深さは $O(\log(\text{値域}))$。

3クエリ $O(\log(\text{値域}))$
根からの各ノードの直線を評価し、$x$ の位置に応じて左か右の子に進む。各ノードを1回ずつ訪れる。

4動的ノード生成
値域が $[-2 \times 10^{18}, 2 \times 10^{18}]$ のように大きい場合、必要に応じて LiChaoNode を生成する遅延初期化を使う。

5オンライン処理
XOR による暗号化を解除 (x = raw_x ^ last_ans) してから Li Chao Tree に問い合わせる。

計算量

直線追加: $O(\log(\text{値域})) \approx O(60)$
クエリ: $O(\log(\text{値域})) \approx O(60)$
全体: $O(Q \log(\text{値域}))$
空間: $O(Q \log(\text{値域}))$（動的ノード）

よくあるミス

ミス	原因	正しい書き方
整数オーバーフロー（C++）	$a \times x$ が $10^{9} \times 10^{18} = 10^{27}$	Python では自動多倍長なので問題なし
最小値クエリと最大値クエリ混同	符号反転し忘れ	最大値は `>` で比較
lo==hi チェックを再帰前にしない	無限再帰	`if lo == hi: return` を必ず入れる
last_ans を初期化しない	XOR が意図した値と異なる	`last_ans = 0` で初期化

次のステップ

発展問題: 直線の削除（removable Li Chao Tree）を実装する
類題: Convex Hull Trick (CHT) とLi Chao Treeの使い分け
応用: 直線追加・最小値クエリへの応用（符号反転して流用）

自己評価

完全理解おおむね理解要復習