Day 037-Q1 | Li Chao Tree（動的直線追加・区間挿入）

問題

平面上に $Q$ 個のクエリ。空の直線集合 $\mathcal{L}$ について順次処理する。

1 a b l r: 区間 $[l, r]$ に限定された直線 $y = ax + b$ を追加。
2 x: 現在の $\mathcal{L}$ で $x$ における値 $ax + b$ の最小を出力。該当無しは INF。

制約

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

$-10^9 \le a, b, x \le 10^9$

$1 \le l \le r \le M$

時間制限: 2sec / メモリ: 256MB

入出力例

入力例 1

5 6
1 2 3 4 5
1 -1 10 1 5
1 1 4 2 4
2 3
2 1
1 0 -5 1 5
2 3

出力例 1

7
5
-5

概念図: Li Chao Tree

セグ木の各ノードに「そのノードの区間で最小値を取る候補直線」を 1 本のみ保持。中点比較で swap し、劣る側を子へ再帰送り。

ヒント (段階的開示)

ヒント1: 方向性

Li Chao Tree は座標を葉に持つセグ木で「ノードあたり最小値候補 1 直線」のみ保持。クエリは葉までのパスで min。

ヒント2: アプローチ

区間 $[l, r]$ への挿入は標準的な区間分解で $O(\log M)$ ノードに分割し、各ノードで通常 add_line。挿入総コスト $O((\log M)^2)$。

ヒント3: add_line のロジック

中点 $m$ で new(m) < cur(m) なら swap し、端で劣る側の子へ再帰。葉に到達したら停止。

def add_line(node, lo, hi, line):
    if seg[node] is None: seg[node]=line; return
    if f(line, mid) < f(seg[node], mid):
        seg[node], line = line, seg[node]
    if lo == hi: return
    if f(line, lo) < f(seg[node], lo):
        recurse left
    else:
        recurse right

模範解答 (Python)

import sys
input = sys.stdin.readline
INF = 10**18

def solve():
    M, Q = map(int, input().split())
    xs = list(map(int, input().split()))
    queries = [input().split() for _ in range(Q)]

    SIZE = 1
    while SIZE < M: SIZE *= 2
    seg = [None] * (4 * SIZE)

    def f(line, i):
        a, b = line
        return a * xs[i] + b

    def add_line(node, lo, hi, a, b):
        stack = [(node, lo, hi, a, b)]
        while stack:
            node, lo, hi, a, b = stack.pop()
            if seg[node] is None:
                seg[node] = (a, b); continue
            ca, cb = seg[node]
            new_line = (a, b); cur_line = (ca, cb)
            mid = (lo + hi) // 2
            left_new = f(new_line, lo) < f(cur_line, lo)
            mid_new  = f(new_line, mid) < f(cur_line, mid)
            if mid_new:
                seg[node] = new_line
                new_line, cur_line = cur_line, new_line
                left_new = not left_new
            if lo == hi: continue
            if left_new:
                stack.append((2*node,   lo,    mid, *new_line))
            else:
                stack.append((2*node+1, mid+1, hi,  *new_line))

    def add_segment(l, r, a, b):
        stack = [(1, 0, SIZE-1, l, r)]
        while stack:
            node, lo, hi, ql, qr = stack.pop()
            if qr < lo or hi < ql: continue
            if ql <= lo and hi <= qr:
                add_line(node, lo, hi, a, b); continue
            mid = (lo+hi)//2
            stack.append((2*node,   lo,    mid, ql, qr))
            stack.append((2*node+1, mid+1, hi,  ql, qr))

    def query(i):
        node, lo, hi = 1, 0, SIZE-1
        best = INF
        while True:
            if seg[node] is not None:
                a, b = seg[node]
                best = min(best, a*xs[i] + b)
            if lo == hi: break
            mid = (lo+hi)//2
            if i <= mid: node, hi = 2*node, mid
            else:        node, lo = 2*node+1, mid+1
        return best

    out = []
    for q in queries:
        if q[0] == '1':
            a = int(q[1]); b = int(q[2])
            l = int(q[3]) - 1; r = int(q[4]) - 1
            add_segment(l, r, a, b)
        else:
            i = int(q[1]) - 1
            v = query(i)
            out.append('INF' if v >= INF else str(v))
    sys.stdout.write('\n'.join(out) + '\n')

solve()

Step-by-Step 解説

1座標の離散化
$x$ 候補が事前に決まっているので添字 $0..M-1$ を葉に持つセグ木が組める。

2セグ木サイズの 2 冪パディング
SIZE = 2^k ≥ M。子ノード番号 $2v / 2v+1$ で安全に再帰可能。

3add_line: 単一ノード処理
中点で優劣判定し swap。両端で劣る側の子に再帰。葉なら停止。

4add_segment: 区間版
$[l, r]$ を $O(\log M)$ ノードに分解し、それぞれで add_line。挿入 $O((\log M)^2)$。

5query
葉までのパス上の全ノード保持直線の min。$O(\log M)$。

計算量

構築: $O(M)$（実質ノード配列のみ）
挿入: $O((\log M)^2)$
クエリ: $O(\log M)$
合計: $O((M + Q)(\log M)^2)$

よくあるミス

ミス	原因	正しい書き方
葉ノードでも子に再帰し無限ループ	葉判定漏れ	`if lo == hi: continue`
add_segment の区間分解漏れ	左右両方を必ず呼んでいない	常に左右を stack push し、不要は `qr<lo or hi<ql` でスキップ
整数オーバーフロー	$ax+b$ が $10^{18}$ に近い	Python は多倍長で安全。C++ は `__int128`
区間外で値が出る	通常 LCT を全区間で使った	区間版 `add_segment` を使う

Day 037-Q1 — Li Chao Tree（動的直線追加・区間挿入対応）

問題

制約