Day 142-Q5 — 線分の上下判定クエリ（Trapezoidal Decomposition簡略版）

2026-09-03 赤色 Master / Phase 8+ ★★★★★★★★★ X軸セグメント木+ノードごとY順ソート済みリストへの二分探索でO(log^2 K)

問題

$xy$平面上に、互いに交差しない（端点で接することも含めて交差しない）$K$本の線分が与えられる。$i$番目の線分は$(x_{1,i},y_{1,i})$から$(x_{2,i},y_{2,i})$まで（$x_{1,i}<x_{2,i}$）とする。

続けて$Q$個のクエリ点$(qx,qy)$が与えられる。各クエリについて、$x=qx$における各線分の$y$座標（$x$座標の範囲に$qx$が含まれるものだけ対象）のうち、$qy$以上でかつ最小となる線分（点から真上に光線を飛ばして最初に当たる線分）の番号を出力せよ。該当なしなら-1を出力せよ。

入力形式

K Q
x1_1 y1_1 x2_1 y2_1
:
x1_K y1_K x2_K y2_K
qx_1 qy_1
:
qx_Q qy_Q

制約

$1 \le K,Q \le 2\times10^5$
$-10^9 \le x_{1,i}<x_{2,i} \le 10^9$
線分同士は互いに交差しない
$-10^9 \le qx,qy \le 10^9$

入出力例

入力例1

3 4
0 5 10 5
0 1 10 3
2 8 6 8
5 4
5 6
5 9
8 2

出力例1

1
3
-1
2

概念図

3線分A,B,Cとクエリ点からの真上探索 A (y=5) B (y:1→3) C (y=8, x∈[2,6]) (5,4) 真上探索 → 最初にA(y=5)に当たる (8,2) x=8はCの範囲外→A,Bのみ対象、最初にB

ヒント（段階的開示）

ヒント1（方向性）

本格的なTrapezoidal Decomposition（乱択増分法による平面の台形分割とDAGによる点位置決定）は実装が複雑。しかし核心の発想——「交差しない線分同士は共通のx区間内では常に同じ上下関係を保つ」——だけを取り出せば、X座標のセグメント木という道具で同じ発想を体験できる。

ヒント2（アプローチ）

各線分をx区間をカバーするO(log K)個のセグメント木ノードに分解して登録し、各ノード内では線分同士をy順にソートしておく。クエリ点は該当する葉から根までのO(log K)個のノードだけを見て、各ノードで二分探索により「qy以上で最小」の線分を求め、全体の最小を取る。

ヒント3（誘導） 
from fractions import Fraction as F
import bisect

def y_at(seg, x):
    x1, y1, x2, y2, idx = seg
    return F(y1) + F(y2 - y1, x2 - x1) * (x - x1)

# 構築時: 各ノードの左端xでy順にソート（交差しない制約で順序は区間全体で保たれる）

def query(qx, qy, xs, size, node_segs):
    leaf = size + leaf_index_of(qx)
    best = None
    node = leaf
    while node >= 1:
        segs = node_segs[node]
        if segs:
            keys = [y_at(seg, qx) for seg in segs]
            j = bisect.bisect_left(keys, qy)
            if j < len(segs):
                yv = keys[j]
                if best is None or yv < best[0]:
                    best = (yv, segs[j][4])
        node //= 2
    return best[1] if best else None

模範解答 (Python)

import sys
from fractions import Fraction as F
import bisect

def main():
    data = sys.stdin.read().split()
    idx = 0
    k, q = int(data[idx]), int(data[idx+1]); idx += 2

    segments = []
    for i in range(k):
        x1, y1, x2, y2 = int(data[idx]), int(data[idx+1]), int(data[idx+2]), int(data[idx+3])
        idx += 4
        segments.append((x1, y1, x2, y2, i + 1))

    def y_at(seg, x):
        x1, y1, x2, y2, _ = seg
        if x2 == x1:
            return F(y1)
        return F(y1) + F(y2 - y1, x2 - x1) * (x - x1)

    xs = sorted(set([s[0] for s in segments] + [s[2] for s in segments]))
    pos = {x: i for i, x in enumerate(xs)}
    m = len(xs) - 1
    size = 1
    while size < max(m, 1):
        size *= 2
    node_segs = [[] for _ in range(2 * size)]

    def update(l, r, seg, node, nl, nr):
        if r <= nl or nr <= l:
            return
        if l <= nl and nr <= r:
            node_segs[node].append(seg)
            return
        mid = (nl + nr) // 2
        update(l, r, seg, node * 2, nl, mid)
        update(l, r, seg, node * 2 + 1, mid, nr)

    for seg in segments:
        l, r = pos[seg[0]], pos[seg[2]]
        update(l, r, seg, 1, 0, size)

    def sort_rec(node, nl, nr):
        if node_segs[node]:
            rep_x = xs[nl]
            node_segs[node].sort(key=lambda seg: y_at(seg, rep_x))
        if nr - nl > 1:
            mid = (nl + nr) // 2
            sort_rec(node * 2, nl, mid)
            sort_rec(node * 2 + 1, mid, nr)
    sort_rec(1, 0, size)

    out = []
    for _ in range(q):
        qx, qy = int(data[idx]), int(data[idx+1]); idx += 2
        i = bisect.bisect_right(xs, qx) - 1
        if i < 0 or i >= len(xs) - 1:
            out.append("-1")
            continue
        node = size + i
        best = None
        while node >= 1:
            segs = node_segs[node]
            if segs:
                keys = [y_at(seg, qx) for seg in segs]
                j = bisect.bisect_left(keys, F(qy))
                if j < len(segs):
                    yv = keys[j]
                    if best is None or yv < best[0]:
                        best = (yv, segs[j][4])
            node //= 2
        out.append(str(best[1]) if best else "-1")

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

main()

Step-by-Step 解説

1線分をセグメント木に載せる
各線分のx区間を座標圧縮したX軸のセグメント木上でO(log K)個のノードに分解して登録する。K本の登録全体でO(K log K)個のエントリが生まれる。
2ノード内ソートが安全な理由
あるノードが担当するx区間全体で登録された線分同士は交差しないため、上下関係が入れ替わらない。区間の左端で一度だけソートしておけば区間内のどのxでも順序が保たれる。
3クエリ処理
qxを含む葉から根までのO(log K)個のノードを見て、各ノードでqxにおける実際のy座標を計算し二分探索する。全ノードの中での最小値が答え。
4交差しない制約が本質的
交差してよいなら区間内で上下関係が入れ替わってしまい本格的な乱択増分法によるTrapezoidal Decompositionが必要になる。本問はその特別な場合の簡略版。
5計算量
構築O(K log^2 K)、クエリ1回あたりO(log^2 K)程度（ノードごとの二分探索コスト込み）。

よくあるミス

ミス原因正しい書き方
各ノードのソートをクエリのたびに行ってしまう交差しない制約により順序が固定されることに気づいていないソートは構築時に一度だけ行い再利用する
ソート基準の1点評価とクエリ時の値をそのまま混同する順序が保たれることと実際の値の再計算を混同している順序は保たれるがy座標の値はqxごとに再計算する
浮動小数点でy座標を計算し際どいケースで誤判定する有理数計算の必要性を見落としているFractionまたはクロス積比較で誤差をなくす
セグメント木のノード区間管理を誤り線分がカバーしないノードにまで登録する区間更新の再帰的分解ロジックにバグがある区間が完全に含まれるノードでのみ登録する標準的な区間更新に従う
クエリのqxがどの線分の区間にも含まれない場合の処理を忘れる該当なしのケースを考慮していないbest is Noneのときは-1を出力する

次のステップ

  • 発展: 線分の追加・削除がオンラインで発生する動的な設定に拡張し、平衡二分探索木でノードごとのソート済みリストを持たせO(log^2 K)の更新・クエリを実現せよ。
  • 発展2: 交差を許した一般の場合に対応する乱択増分法による本格的なTrapezoidal Decompositionを実装し、本問の簡略版との計算量・実装量を比較せよ。

自己評価

自分の回答

気づき・メモ