Day 124-Q2 — Li Chao Tree on Segment Tree（区間ごとの直線集合を管理する二重データ構造）

問題

$x$ 座標は $1$ から $N$ の整数で表される。以下の2種類のクエリを $Q$ 個、オンラインで順に処理せよ。

- 1 l r a b: 直線 $y = ax + b$ を追加する。ただしこの直線は $x \in [l, r]$ の範囲でのみ「有効」とする（それ以外の $x$ では存在しないものとして扱う） - 2 x: これまでに追加された直線のうち、$x$ を有効範囲に含むものすべての中で、$y = ax+b$ の最小値を出力する（該当する直線が1本もなければ INF と出力）

入力形式

N Q
query_1
...
query_Q

制約

入出力例

5 4
1 1 5 2 3
2 3
1 2 4 -1 10
2 3

9
7

概念図

ヒント（段階的開示）

def seg_update(node, lo, hi, l, r, a, b):
    if r < lo or hi < l: return
    if l <= lo and hi <= r:
        lichao_roots[node] = lc_insert(lichao_roots[node], 1, N, a, b)
        return
    mid = (lo+hi)//2
    seg_update(2*node, lo, mid, l, r, a, b)
    seg_update(2*node+1, mid+1, hi, l, r, a, b)

模範解答 (Python)

📋 コピーimport sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    INF = float('inf')

    # --- Li Chao Tree (pointer-based, domain [1, N] 固定) ---
    class LC:
        __slots__ = ['a', 'b', 'left', 'right']
        def __init__(self, a, b):
            self.a = a
            self.b = b
            self.left = None
            self.right = None

    def lc_insert(node, lo, hi, a, b):
        if node is None:
            return LC(a, b)
        mid = (lo + hi) // 2
        l_new = a * lo + b < node.a * lo + node.b
        m_new = a * mid + b < node.a * mid + node.b
        if m_new:
            node.a, node.b, a, b = a, b, node.a, node.b
        if lo == hi:
            return node
        if l_new != m_new:
            node.left = lc_insert(node.left, lo, mid, a, b)
        else:
            node.right = lc_insert(node.right, mid + 1, hi, a, b)
        return node

    def lc_query(node, lo, hi, x):
        if node is None:
            return INF
        res = node.a * x + node.b
        if lo == hi:
            return res
        mid = (lo + hi) // 2
        if x <= mid:
            return min(res, lc_query(node.left, lo, mid, x))
        else:
            return min(res, lc_query(node.right, mid + 1, hi, x))

    # --- 外側セグメント木（各ノードは Li Chao Tree のルートを保持） ---
    size = 1
    while size < N:
        size *= 2
    lichao_roots = {}

    def seg_update(node, lo, hi, l, r, a, b):
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            lichao_roots[node] = lc_insert(lichao_roots.get(node), 1, N, a, b)
            return
        mid = (lo + hi) // 2
        seg_update(2 * node, lo, mid, l, r, a, b)
        seg_update(2 * node + 1, mid + 1, hi, l, r, a, b)

    def seg_query(node, lo, hi, x):
        res = lc_query(lichao_roots.get(node), 1, N, x)
        if lo == hi:
            return res
        mid = (lo + hi) // 2
        if x <= mid:
            return min(res, seg_query(2 * node, lo, mid, x))
        else:
            return min(res, seg_query(2 * node + 1, mid + 1, hi, x))

    out = []
    sys.setrecursionlimit(300000)
    for _ in range(Q):
        t = input_data[idx]; idx += 1
        if t == '1':
            l = int(input_data[idx]); idx += 1
            r = int(input_data[idx]); idx += 1
            a = int(input_data[idx]); idx += 1
            b = int(input_data[idx]); idx += 1
            seg_update(1, 1, N, l, r, a, b)
        else:
            x = int(input_data[idx]); idx += 1
            res = seg_query(1, 1, N, x)
            out.append(str(res) if res != INF else "INF")

    print('\n'.join(out))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 区間ごとに有効な直線を「追加だけでなく削除もできる」ようにするには、区間を時間軸に見立ててオフラインで処理する「セグメント木上のUndo可能なLi Chao Tree」（オフライン動的Li Chao Tree）に一般化できる。
• 次回予告: Weighted Matroid Union（重み付きマトロイド合併・K-forest分割問題）

自己評価

自分の回答

気づき・メモ