まず、こうした問題では円周を切り開いて直線上の問題にしても結論が変わらないことが知られているので、そのようにして考えます。すると、\(j\) 番目のクエリはある \(l_j \leq s, t \leq r_j\) であって

\[A_s \lt A_t \lt B_s \lt B_t\]

を満たすものがあれば No 、そうでなければ Yes となります。\(l_j \leq s \leq r_j\) の範囲にある区間 \([A_s, B_s]\) の集合がラミナー族をなすかどうかを判定する問題ともいえます。

複数のクエリを処理する方法として尺取り法を用いることを考えましょう。尺取り法により各 \(1 \leq L \leq N\) に対してクエリ \((L, R)\) の答えが Yes となる最大の \(R\) を計算できれば全てのクエリに回答できます。尺取り法内部で処理が必要なクエリは次の通りです：

• 区間の集合 \(S\) がある。はじめ \(S\) は空である。以下のクエリを処理せよ。
  • ラミナー族である \(S\) に区間 \([a,b]\) を追加した後もラミナー性が保たれるかを判定する。
  • \(S\) に区間 \([a,b]\) を追加する。追加後も \(S\) はラミナー族である必要がある。
  • \(S\) から \([a,b] \in S\) を満たす区間 \([a,b]\) を削除する。

言い換えた後のクエリを処理する方法を考えましょう。ここからはいくつか解法がありますが、ここではハッシュを用いた解法を紹介します。(ただし乱択アルゴリズムです)

長さ \(2N+1\) の数列 \(C\) を考えます。\(C\) の要素は全て \(0\) です。
区間 \([a,b]\) を \(S\) に追加するたびに \(i \in [a,b)\) について \(C_i\) に変数 \(x_{a,b}\) を加算することを考えます。(削除の時はこの逆操作を行います。)すると、\(S\) に \([a,b]\) を追加できるかどうかの判定は \(C_a = C_{b-1}\) で判定できます。証明については、\(c \lt a \lt d \lt b\) あるいは \(a \lt c \lt b \lt d\) を満たす \([c,d]\) が \(S\) に含まれているときかつその時に限り \(C_a, C_{b-1}\) の丁度一方に \(x_{c,d}\) が加算されることから従います。 よってこの方法によってクエリ処理が可能となりました。
後は各 \(x_{a,b}\) に乱数を割り当てて高速化(zobrist hash)したものをセグメント木に載せればよいです。計算量は \(\mathrm{O}(N \log N + Q)\) で十分高速です。

• 実装例, C++