この解説では \(2\) つの区間 \(I, J\) が交差するとは、\(I\setminus J, J\setminus I\) がともに空でないことを表すこととします。

点 \(1\) と点 \(N\) の間で円を切り開くことで、「他の線分と交わらない線分を書く」という問題を「他の区間と交差しない区間を書く」という問題に置き換えることができます。

セグメント木による解法1

区間 \([A_i,B_i]\) が既に書かれた他の区間と交差することは、既に書かれた区間に「\(A_i\) を含むが \(B_i\) を含まない区間」または「\(B_i\) を含むが \(A_i\) を含まない区間」が存在することと同値です。そのような区間が存在するか判定する方法を考えます。

既に書かれた区間のうち点 \(A_i\) を含むものを長い順に \(I_1=[A'_1,B'_1],\ldots,I_k=[A'_k,B'_k]\) とすると、これらは互いに交差しないことから、\(A'_1<\dots<A'_k<A_i<B'_k<\dots<B'_1\) となります。よってこれらの区間全てが \(B_i\) を含むことは、\(I_k\) が \(B_i\) を含むことと同値です。

これは「各 \(i\) について、既に書かれた区間のうち点 \(i\) を含む最も短いもの」を求めることができれば判定することができます。各クエリはではこの情報の1点取得/区間更新を行うため、遅延セグメント木(双対セグメント木)を用いることで高速に判定/更新を行うことができます。

セグメント木による解法2

各区間の始め ( を、終わりに ) を置くことを考えます。既に書かれた区間は互いに交差しないことから、区間 \([A_i,B_i]\) が既に書かれた他の区間と交差しないことは、この区間だけを取り出したとき正しいカッコ列ができることと同値です。よって、(, ) をそれぞれ \(1\), \(-1\) に置き換えた列のprefix和の最小値と区間和を保持するセグメント木により判定することができます。

（正しいカッコ列である \(\iff\) (, ) をそれぞれ \(1\), \(-1\) に置き換えた列のprefix和の最小値が \(0\) かつ区間和が \(0\) である）

セグメント木による解法3

区間 \([A_i,B_i]\) が既に書かれた他の区間と交差することは、既に書かれた区間に「\(L< A_i\) かつ \(A_i \leq R < B_i\) となる区間 \([L,R]\) 」または「\(A_i\leq L< B_i\) かつ \(B_i<R\) となる区間 \([L,R]\) 」が存在することと同値です。よって、セグメント木であって、区間 \([l,r)\) に対応する各ノードが「\(l \leq R < r\) となる区間 \([L,R]\) に関する \(L\) の最小値」「\(l \leq L < r\) となる区間 \([L,R]\) に関する \(R\) の最小値」の \(2\) つを保持するものを用いて判定することができます。

ハッシュによる解法

区間 \(I\) が区間 \(J\) と交差しないことは、\(I\) に \(J\) の端点が偶数個含まれることと同値です。

よって、各区間の端点に適当な値を割り当て、区間 \(I\) 内の点に割り当てられた値のXORが \(0\) であるかどうかで判定することができます。

hash が \(B\) - bitであるとき、誤判定する確率は高々 \(\frac{1}{2^B}\) であることから、\(1-\frac{Q}{2^B}\) 程度の確率でACを得ることができます。