In this editorial, we say that an interval \(I\) cross an interrval \(J\) if \(I\setminus J\) and \(J\setminus I\) are both non-empty.

By cutting and unrolling the circle between points \(1\) and \(N\), the problem asking to “draw a segment that does not intersect with others” can be regarded as asking to “place an interval that does not cross others.”

Segment tree solution 1

An interval \([A_i,B_i]\) crosses another already-drawn interval if and only if there exists a drawn interval that contains \(A_i\) but does not contain \(B_i\), or that contains \(B_i\) but does not contain \(A_i\). We consider how to determine the existence.

Among drawn intervals, suppose that intervals \(I_1=[A'_1,B'_1],\ldots,I_k=[A'_k,B'_k]\) contain \(A_i\), enumerated in descending order of their lengths. Since they do not cross each other, \(A'_1<\dots<A'_k<A_i<B'_k<\dots<B'_1\). Thus, these intervals all contain \(B_i\) if and only if \(I_k\) does.

This can be determined if we can, given an \(i\), find the shortest already-drawn interval containing point \(i\). Each query requires this element-wise retrieval and a segment-wise update, which can be achieved by a lazy segment tree (dual segment tree).

Segment tree solution 2

Consider placing ( at the beginning of each interval and ) at the end. Since already-drawn intervals do not cross each other, interval \([A_i,B_i]\) does not cross another drawn intervals if and only if the symbols written within this interval forms a valid parenthesis sequence. By replacing ( and ) with \(1\) and \(-1\), respectively, the validness can be determined by a segment tree that supports retrieval of the minimum prefix sum and the pure sum within the interval.

(They form a valid parenthesis sequence \(\iff\) after replacing ( with \(1\) and ) with \(-1\), the minimum prefix sum is \(0\) and segment sum is \(0\))

Segment tree solution 3

An interval \([A_i,B_i]\) crosses another already-drawn interval if and only if there exists a drawn interval \([L,R]\) such that \(L< A_i\) and \(A_i \leq R < B_i\), or \(A_i\leq L< B_i\) and \(B_i<R\). This condition can be checked with a segment tree whose node corresponding to \([l,r)\) maintains two values: the minimum \(L\) among the intervals \([L,R]\) with \(l \leq R < r\), and the minimum \(R\) among the intervals \([L,R]\) with \(l \leq L < r\).

Hash solution

An interval \(I\) crosses an interval \(J\) if and only if \(I\) contains an even number of endpoints of \(J\).

Therefore, by assigning a random value to both endpoints of each segment, one can determine this criteria by checking if the XOR (exclusive logical sum) of the numbers assigned to the points within the interval \(I\) is \(0\).

When the hash as \(B\) bits, the probability of false positive is at most \(\frac{1}{2^B}\), so it prints a correct answer with probability about \(1-\frac{Q}{2^B}\).