Day 112-Q3 | Kinetic Segment Tree

問題

$N$個のスロットがあり、スロット$i$は一次関数$f_i(t)=a_i t+b_i$を持つ。時刻は$t=1$から始まりクエリ1個ごとに1進む。0 i a b（スロット$i$の関数を更新）と1 l r（このクエリの時刻$t$での$\min_{l\le i\le r}f_i(t)$を出力）を順に処理せよ。

入力形式

N Q
a_1 b_1
...
a_N b_N
query_1
...
query_Q

制約

$1 \le N, Q \le 2\times10^5$

$-10^9 \le a_i, b_i \le 10^9$

$1 \le l \le r \le N$

入出力例

入力例1

出力例1

t=1: 11,18,5→最小5。t=2: 12,16,5→最小5。t=3でスロット3をf(t)=3t-100に更新。t=4: 14,12,-88→最小-88。t=5: f2=10,f3=-85→最小-85。

概念図: certificate（証拠の期限）で再計算を最小限にする

ヒント（段階的開示）

ヒント1: 方向性

各要素の値が時刻とともに変化するため、通常のセグ木のように固定値では扱えない。毎クエリ全走査は$O(NQ)$で間に合わない。「順序が変わる瞬間」だけを検知して再計算するKinetic Data Structuresの発想を使う。

ヒント2: アプローチ

各ノードに現在の勝者ポインタ`win`を持たせ、2子の勝者同士の交点(certificate)をイベントキューに登録する。証拠が切れたノードだけをキューから取り出し再計算(melt)し、親まで伝播する。区間クエリはO(log N)個の分解ノードの`win`を直接読むだけでよい。

ヒント3: 誘導（コード骨格）

def pull(node, t):
    wl, wr = win[l], win[r]
    w, o = (wl, wr) if value(wl,t)<=value(wr,t) else (wr, wl)
    win[node] = w
    da = a0[w] - a0[o]
    if da > 0:
        t0 = Fraction(b0[o]-b0[w], da)
        cert = floor(t0) + 1
        heappush(heap, (cert, node, ver[node]))

def process_heap(t):
    while heap and heap[0][0] <= t:
        cert, node, v = heappop(heap)
        if v != ver[node]: continue
        pull(node, t); propagate_up(node, t)

模範解答 (Python)

import sys, heapq, math
from fractions import Fraction

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1

    size = 1
    while size < N:
        size *= 2
    BIG = 1 << 60
    a0 = [0] * size
    b0 = [BIG] * size
    for i in range(N):
        a0[i] = int(data[idx]); idx += 1
        b0[i] = int(data[idx]); idx += 1

    win = [0] * (2 * size)
    for p in range(size):
        win[size + p] = p
    ver = [0] * (2 * size)
    heap = []

    def value(i, t):
        return a0[i] * t + b0[i]

    def pull(node, t):
        l, r = node * 2, node * 2 + 1
        wl, wr = win[l], win[r]
        if value(wl, t) <= value(wr, t):
            w, o = wl, wr
        else:
            w, o = wr, wl
        win[node] = w
        da = a0[w] - a0[o]
        db = b0[w] - b0[o]
        ver[node] += 1
        if da > 0:
            t0 = Fraction(-db, da)
            cert = math.floor(t0) + 1
            if cert <= t:
                cert = t + 1
            heapq.heappush(heap, (cert, node, ver[node]))

    for node in range(size - 1, 0, -1):
        pull(node, 0)

    def propagate_up(node, t):
        nd = node // 2
        while nd >= 1:
            pull(nd, t)
            nd //= 2

    def update(pos, a, b, t):
        a0[pos] = a
        b0[pos] = b
        propagate_up(size + pos, t)

    def process_heap(t):
        while heap and heap[0][0] <= t:
            cert, node, v = heapq.heappop(heap)
            if ver[node] != v:
                continue
            pull(node, t)
            propagate_up(node, t)

    def query(l, r, t):
        process_heap(t)
        best = None
        li, ri = l + size, r + size + 1
        while li < ri:
            if li & 1:
                v = value(win[li], t)
                if best is None or v < best:
                    best = v
                li += 1
            if ri & 1:
                ri -= 1
                v = value(win[ri], t)
                if best is None or v < best:
                    best = v
            li //= 2; ri //= 2
        return best

    out = []
    t = 0
    for _ in range(Q):
        t += 1
        typ = data[idx]; idx += 1
        if typ == "0":
            pos = int(data[idx]) - 1; idx += 1
            a = int(data[idx]); idx += 1
            b = int(data[idx]); idx += 1
            update(pos, a, b, t)
        else:
            l = int(data[idx]) - 1; idx += 1
            r = int(data[idx]) - 1; idx += 1
            out.append(str(query(l, r, t)))

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

main()

計算量: melt回数は償却$O((N+Q)\log N)$程度、1回の伝播が$O(\log N)$で全体概ね$O((N+Q)\log^2 N)$。愚直$O(N)$走査の参照実装との突き合わせ（数百ケース）で全出力一致を確認済み。

Step-by-Step 解説

1セグ木の葉と勝者ポインタ
各ノードは値そのものではなく「どのスロットが現在最小か」というポインタ(win)を持つ。

2certificateという考え方
2直線の交点を「証拠の有効期限」として記録し、その時刻までwinが正しいことを保証する。

3期限切れノードだけ再計算する
優先度付きキューから期限切れイベントだけを取り出しmeltする。

4再計算は必ず根まで伝播させる
子のwinが変われば親の比較結果も変わりうるため祖先を順にpullし直す。

5バージョン管理で古いイベントを無視する
再計算のたびにver[node]を増やし、キューから取り出したイベントのバージョンが一致しなければ読み捨てる。

よくあるミス

ミス	原因	正しい書き方
meltしたノード自身だけ再計算し親への伝播を忘れる	「証拠が切れたノードだけ直せば十分」と誤解する	melt後は必ずpropagate_upで根まで伝播させる
証拠の期限を浮動小数点で計算し誤差で境界がずれる	floatの丸め誤差が整数時刻判定に影響する	Fractionで厳密に交点を計算しfloor(t0)+1で最初の整数時刻を求める
傾きが同じ場合にゼロ除算や誤った証拠を作る	da=0のケースを特別扱いしない	da<=0のときは証拠なし（無期限）として扱う
クエリ前にprocess_heap(t)を呼び忘れる	分解ノードのwinが古いままになる	区間クエリの直前に必ず現在時刻までのイベントを処理する

次のステップ

発展: 最小値のインデックスも出力するよう拡張しタイブレークを定義する
発展: 優先度が時間とともに線形変化するスケジューリング問題に応用する
発展: Li Chao Treeとの使い分けを整理する

自己評価

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

Day 112-Q3 — Kinetic Segment Tree（動く一次関数群の区間最小値）

問題