P - 線引きゲーム/Connect the Dots 解説
by 
Nyaan
For problems of this kind, it is known that cutting the circle open and considering the problem on a line does not change the conclusion, so we do that here. The answer to the \(j\)-th query is then No if there exist \(l_j \leq s, t \leq r_j\) satisfying
\[A_s \lt A_t \lt B_s \lt B_t\]
and Yes otherwise. Equivalently, we need to determine whether the collection of intervals \([A_s, B_s]\) for \(l_j \leq s \leq r_j\) forms a laminar family.
Consider using the two-pointer method to process multiple queries. If we compute, for each \(1 \leq L \leq N\), the maximum \(R\) for which query \((L, R)\) has answer Yes, we can answer every query. The operations needed inside the two-pointer method are as follows:
- We have a collection \(S\) of intervals. Initially, \(S\) is empty. Process the following queries:
- Determine whether adding an interval \([a,b]\) to the laminar family \(S\) preserves the laminar property.
- Add an interval \([a,b]\) to \(S\). The resulting \(S\) must remain a laminar family.
- Remove an interval \([a,b]\) satisfying \([a,b] \in S\) from \(S\).
Let us consider how to process these reformulated queries. There are several solutions; here we introduce one using hashing. (This is a randomized algorithm.)
Consider a sequence \(C\) of length \(2N+1\). All elements of \(C\) are initially \(0\).
Whenever an interval \([a,b]\) is added to \(S\), add a variable \(x_{a,b}\) to \(C_i\) for \(i \in [a,b)\). (For deletion, perform the inverse operation.) We can then determine whether \([a,b]\) can be added to \(S\) by checking \(C_a = C_{b-1}\). To see why, an interval \([c,d]\) in \(S\) contributes \(x_{c,d}\) to exactly one of \(C_a, C_{b-1}\) if and only if \(c \lt a \lt d \lt b\) or \(a \lt c \lt b \lt d\). This gives a way to process the queries.
Finally, assign a random value to each \(x_{a,b}\) to make this efficient (Zobrist hashing), and maintain the resulting data in a segment tree. The time complexity is \(\mathrm{O}(N \log N + Q)\), which is sufficiently fast.