Thread Cutting

For distinct $x,a,b$, define

$$\operatorname{mid}(x;a,b)=[\min(a,b)<x<\max(a,b)].$$

For four distinct nails $a,b,c,d$, chords $ab$ and $cd$ cross exactly when

$$\operatorname{mid}(c;a,b)\mathbin{\mathrm{XOR}}\operatorname{mid}(d;a,b)=1.$$

Fix $E_i=P_iP_{i+1}$. XORing its crossing indicators with cancels every intermediate endpoint and leaves

$$\operatorname{mid}(P_{i+2};P_i,P_{i+1})\mathbin{\mathrm{XOR}}\operatorname{mid}(P_R;P_i,P_{i+1}).$$

Let $B_i=\operatorname{mid}(P_{i+2};P_i,P_{i+1})$ and build its prefix XOR array . Since

$$\operatorname{mid}(x;a,b)=[a<x]\mathbin{\mathrm{XOR}}[b<x],$$

XORing the terms involving $P_R$ for $i=L,\cdots,R-3$ cancels all internal comparisons and leaves

$$\operatorname{mid}(P_R;P_L,P_{R-2}).$$

The answer is $0$ when $R-L+1\leq3$. Otherwise it is

$$S_{R-3}\mathbin{\mathrm{XOR}}S_{L-1}\mathbin{\mathrm{XOR}}\operatorname{mid}(P_R;P_L,P_{R-2}).$$

Preprocessing takes $O(N)$ time, and each query takes $O(1)$ time. The total complexity is $O(N+Q)$.

Solution written by GPT5