Day 128-Q1 — Convex Hull Trick（単調CHT）

2026-08-20 赤色 Master / Phase 8+ ★★★★★★★★★ 傾き単調な直線群+クエリx単調の二重の単調性でO(1)償却の追加・クエリ

問題

$N$ 個のクエリを順に処理する。1 A Bで直線 $y=Ax+B$ を追加、2 Xでこれまで追加した全直線について $x=X$ における最小値を出力する。保証: タイプ1の $A$ は出現順に厳密減少、タイプ2の $X$ は出現順に単調非減少。

入力形式

N
query_1
query_2
...
query_N

制約

$1 \le N \le 200000$
$-10^9 \le A,B,X \le 10^9$
タイプ1の $A$ は出現順に厳密減少
タイプ2の $X$ は出現順に単調非減少

入出力例

入力例1

7
1 2 0
1 1 1
1 -1 5
2 0
2 1
2 2
2 3

出力例1

0
2
3
2

直線 y=2x, y=x+1, y=-x+5 を追加。x=0→0, x=1→2(タイ), x=2→3(タイ), x=3→2。

概念図

下側凸包（傾き減少順に追加） x y y=2x y=x+1 y=-x+5 太線=実際に最小値を与える下側凸包。破線区間は他の直線に隠れて不要。

ヒント（段階的開示）

ヒント1（方向性）

直線1本追加ごとに全直線で $x=X$ を計算すると $O(NQ)$ で間に合わない。Li Chao Treeは既習だが、今回は「傾きが追加順に単調減少」かつ「クエリの$x$も単調非減少」という強い制約がある特殊ケース。この二重の単調性を使うと、Li Chao Treeより軽い「単調CHT」が構成できる。

ヒント2（アプローチ）

直線を下側凸包として配列（実質スタック）で管理する。傾き減少順に追加すると不要になる直線が末尾から出るので pop しながら追加すると償却$O(1)$。クエリは $x$ が単調非減少なので、最小値を与える直線を指すポインタは前にしか進まず、これも償却$O(1)$。

ヒント3（誘導） 
def bad(l1, l2, l3):
    a1, b1 = l1
    a2, b2 = l2
    a3, b3 = l3
    return (b3 - b1) * (a1 - a2) <= (b2 - b1) * (a1 - a3)

直線追加時は bad(hull[-2], hull[-1], new_line) が真の間 pop してから追加。クエリ時は「次の直線の方が現在より $x$ で以下」なら ptr を進める。

模範解答 (Python)

import sys


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

    hull = []  # (a, b) : y = a*x + b、傾き減少順に並ぶ下側凸包
    ptr = 0
    out = []

    def bad(l1, l2, l3):
        a1, b1 = l1
        a2, b2 = l2
        a3, b3 = l3
        return (b3 - b1) * (a1 - a2) <= (b2 - b1) * (a1 - a3)

    for _ in range(n):
        t = int(data[idx]); idx += 1
        if t == 1:
            a = int(data[idx]); idx += 1
            b = int(data[idx]); idx += 1
            line = (a, b)
            while len(hull) >= 2 and bad(hull[-2], hull[-1], line):
                hull.pop()
            hull.append(line)
            if ptr > len(hull) - 1:
                ptr = len(hull) - 1
        else:
            x = int(data[idx]); idx += 1
            while ptr + 1 < len(hull) and hull[ptr + 1][0] * x + hull[ptr + 1][1] <= hull[ptr][0] * x + hull[ptr][1]:
                ptr += 1
            a, b = hull[ptr]
            out.append(str(a * x + b))

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


solve()

Step-by-Step 解説

1下側凸包の維持
傾き減少順に追加される直線を、必要な直線だけ配列に保持する。末尾2本と新直線で「真ん中が不要か」を判定し、不要なら pop してから再判定する（monotone chain と同じ発想）。
2bad判定の意味
$l_1,l_3$の交点のy座標が$l_2$上のそれ以下なら$l_2$は不要。分母の符号を揃えた整数の外積比較で浮動小数点誤差を回避する。
3クエリの単調ポインタ
xが単調非減少なので、次の直線の方が現在以下の間 ptr を進める。戻る必要がなく総移動量がhullサイズを超えないため償却$O(1)$。
4追加とポインタの整合性
popでhullが短くなった場合、ptrが範囲外を指さないようptr = min(ptr, len(hull)-1)で補正する。
5計算量
追加・クエリともに償却$O(1)$、全体で$O(N)$。

よくあるミス

ミス原因正しい書き方
bad判定を浮動小数点の交点計算で書くfloat比較の誤差蓄積整数のみの外積形式で判定する
xが単調でないのに単調ポインタ法を適用前提条件の確認不足単調性がない場合は二分探索版CHTやLi Chao Treeを使う
直線追加時にptrが範囲外を指すpop後の長さとptrの不整合追加ごとにptr = min(ptr, len(hull)-1)で補正
bad の等号条件を誤る<=と<の混同同じ最小値を与える直線が複数あってもよいなら<=で積極的に消す

次のステップ

  • 発展: xが単調でない場合は非単調CHT（二分探索）、直線が動的に増減するならLi Chao Treeを使う
  • 次回予告: Kd-tree（k次元空間の最近傍探索・軸交互分割）

自己評価

自分の回答

気づき・メモ