PAST5N
https://gyazo.com/c0b27c17755f5bd753462bf179457248
初回考察
バスの辺に年齢の上限、下限があり、与えられた年齢がその範囲に収まっているときだけ辺が存在するとみなして到達可能範囲を求める問題
年齢軸を時間軸にする
下限でつなぎ、上限で外せば良い
クエリは先読みして、混ぜてソートする
PAST2NではRange Addだったけど、今回はそうではない、どうするか？ 繋がってる範囲の右端と左端が高速に得られれば良い
右端を持つフェニック木と左端を持つフェニック木を用意すれば良い
ある位置が与えられた時に、そこより左にある最も近い左端を見つけるのは二分探索で対数オーダー
見つけた左端より右で最も近い右端を見つければ範囲がわかる
クエリで与えられた位置がその範囲に入ってれば、それが答え
考察完了
公式解説
解法1
年齢でソート
道が通れるかどうかは高々2回しか変化しない
僕の考察と同じ
平衡二分木だから、ということだね
解法2
Lをmaxのセグメント木にする
Range maxを使った二分探索が対数オーダーになる
下限の制約に違反しない範囲が求まる
Rについても同様にする