解法 1

まず最初に質問を全て読み込み、年齢の昇順にソートします。
これを前から順に答えていくことを考えます。このとき、旅をする人間の年齢は(広義)単調増加なため、\(Q\) 個のクエリを答える過程で \(N - 1\) 本の道路の通れるかどうかの状態はそれぞれ高々 \(2\) 回(年齢下限を通過したときと、上限を通過したとき) 変化します。
通れない道路の番号を std::set などで管理すれば、都市 \(B_i\) から辿りつける最大の都市番号と最小の都市番号が set.lower_bound() などで \(O(\log(N))\) で求まります
計算量は \(O((N + Q) \log(N))\) です。

解法 2

\(L\) をセグメント木に載せます。\([B_i, j)\) の最大値が \(A_i\) を超えないような最大の \(j\) を求めるセグ木上の二分探索で、年齢下限に違反せずに行くことのできる最大の都市番号を \(O(\log(N))\) で求めることができます。
\(R\) もセグメント木に載せ同様の二分探索をすることで、年齢上限に違反せずに行くことのできる最大の都市番号も \(O(\log(N))\) で求めることができます。
更にこれを都市番号の大きい向きだけではなく小さい向きにもすることで、辿りつける範囲を求めることができます。
計算量は \(O(N + Q \log(N))\) です。