Day 043-Q1 — Kinetic Tournament（動的最小値追跡）

2026-05-27 赤色 Master / Phase 8+ ★★★★★★★★★ Kinetic Segment Tree + 一次関数群

問題

$N$ 個の要素があり、各要素 $i$ は時刻 $t$ において値 $f_i(t) = a_i \cdot t + b_i$ を持つ（一次関数）。 $Q$ 個のクエリを処理せよ。

制約

$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$-10^9 \le a_i, b_i \le 10^9$
$0 \le t \le 10^9$
時間制限: 3sec / メモリ: 512MB

クエリ種別

種別形式意味
更新1 i a b要素 $i$ の関数を $a \cdot t + b$ に変更
クエリ2 t時刻 $t$ における $\min_i f_i(t)$ を答える

入出力例

入力例 1

3 4
1 5
-1 9
2 1
2 2
2 4
1 2 -1 9
2 3

出力例 1

5
3
-3

概念図: Kinetic Segment Tree

セグメント木上の一次関数群（時刻 t での最小値追跡） min(f1,f2,f3) winner変わる時刻を記録 min(f1, f2) 交点時刻: cert_t f3 のみ 葉ノード f1(t) = t + 5 a=1, b=5 t=0: 5, t=5: 10 f2(t) = -t + 9 a=-1, b=9 t=0: 9, t=5: 4 f3(t) = 2t + 1 a=2, b=1 t=0: 1, t=5: 11 f1 と f2 の交点: t = (9-5)/(1-(-1)) = 2 更新時: 葉→根方向に証明書を再計算

ヒント（段階的開示）

ヒント1: 方向性
Kinetic Data Structure の考え方。各要素の値が時間の関数で変化するとき、「誰が最小か」を追跡する構造を Kinetic Heap / Kinetic Tournament と呼ぶ。 セグメント木の各内部ノードに「左右子の最小値が入れ替わる時刻（Kinetic Certificate）」を保持する。
ヒント2: アプローチ
  1. セグメント木の葉に $(a_i, b_i)$ を格納
  2. クエリ時、再帰的に左右子の最小を比較して $O(\log N)$ で最小値を得る
  3. 更新時は葉を書き換え、親ノードへ証明書を更新（$O(\log N)$）
  4. 証明書 = 二直線の交点時刻 $t^* = (b_L - b_R) / (a_R - a_L)$
ヒント3: 実装骨格 
# セグメント木で各葉に (a, b) を格納
# クエリ: query_segtree(1, t, 0, size)
def query_segtree(v, t, lo, hi):
    if lo + 1 == hi:
        return tree_a[v] * t + tree_b[v]
    mid = (lo + hi) >> 1
    lv = query_segtree(2*v, t, lo, mid)
    rv = query_segtree(2*v+1, t, mid, hi)
    return min(lv, rv)

# 更新: O(log N) で葉のみ更新
def update(pos, a, b):
    i = size + pos
    tree_a[i] = a
    tree_b[i] = b

模範解答 (Python)

import sys
input = sys.stdin.readline

def solve():
    N, Q = map(int, input().split())
    funcs = []
    for _ in range(N):
        a, b = map(int, input().split())
        funcs.append((a, b))

    size = 1
    while size < N:
        size <<= 1

    tree_a = [0] * (2 * size)
    tree_b = [10**18] * (2 * size)

    for i in range(N):
        tree_a[size + i] = funcs[i][0]
        tree_b[size + i] = funcs[i][1]

    def update(pos, a, b):
        i = size + pos
        tree_a[i] = a
        tree_b[i] = b

    def query_segtree(v, t, lo, hi):
        if lo + 1 == hi:
            return tree_a[v] * t + tree_b[v]
        mid = (lo + hi) >> 1
        lv = query_segtree(2*v, t, lo, mid)
        rv = query_segtree(2*v+1, t, mid, hi)
        return min(lv, rv)

    for _ in range(Q):
        line = input().split()
        if line[0] == '1':
            _, i, a, b = line
            update(int(i) - 1, int(a), int(b))
        else:
            t = int(line[1])
            print(query_segtree(1, t, 0, size))

solve()

Step-by-Step 解説

1Kinetic Data Structure の概念
要素の値が時間とともに変化するデータ構造。一次関数 $f_i(t) = a_i t + b_i$ では「誰が最小か」が時刻 $t^*$ で入れ替わる。この入れ替わり時刻を Kinetic Certificate と呼ぶ。
2セグメント木による実装
葉に $(a_i, b_i)$ を格納し、クエリ時に再帰的に左右子の評価値を比較して最小値を返す。単純実装では $O(N)$ / クエリだが、内部ノードに勝者情報を保存することで $O(\log N)$ を達成できる。
3証明書（Certificate）の管理
各内部ノードに「現在の勝者が変わる最小時刻 $t^*$」を格納。時刻が単調増加するクエリ列では証明書の有効性チェックのみで差分更新が可能（Kinetic Heap の本領）。
4更新操作の流れ
葉の $(a, b)$ を更新 → 親ノードへ向かって証明書を再計算 → $O(\log N)$ ステップで完了。

計算量

クエリ（再帰的最小）: $O(N)$ 素朴 / $O(\log N)$ 証明書管理版
更新: $O(\log N)$
全体: $O((N + Q) \log N)$
空間: $O(N)$

よくあるミス

ミス原因正しい書き方
Li Chao Tree に動的更新を混在LCT は静的クエリ向けKinetic Segment Tree を使う
size を N のまま使う2の冪に揃えていないwhile size < N: size <<= 1
t=0 での割り算エラー交点計算で分母=0a1 == a2 のケースを別処理
初期値の番兵が小さすぎる負の a_i での誤判定番兵を十分大きな値に設定

次のステップ

  • 発展問題: Kinetic Heapment（最小値だけでなく上位K個を追跡）
  • 類題: CF 1178G "The Awesomest String"、IOI 2011 "Race"
  • 応用: 競技ゲームシミュレーション・動的価格最適化

自己評価