オフラインで \(O((N+M+Q)\log N)\) の解法です。

クエリを \(p_i\) の昇順にソートしておきます。与えられた問題は始点が \(p_i\) 以上であるような列車のうち終点が \(q_i\) 以下であるものの個数なので、これは一点更新と区間和取得のできるデータ構造で高速に処理できます。

具体的には、例えば長さ \(N\) のセグメントツリーを全ての \(R\) の位置に \(1\) を加算した状態で初期化し、クエリを処理しながら \(p_i\) が増えるごとに \(L\) が条件を満たさなくなった列車の \(R\) について \(1\) を減算していく、などでこの問題を解くことができます。