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