실 자르기

서로 다른 $x,a,b$에 대해

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

로 정의하자. 서로 다른 네 못 $a,b,c,d$에 대해 현 $ab$와 $cd$의 교차 여부는

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

이다.

$E_i=P_iP_{i+1}$를 고정하자. $E_i$와 $E_{i+2},E_{i+3},\cdots,E_{R-1}$의 교차 횟수의 홀짝은 중간 항의 망원 소거로

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

가 된다.

$B_i=\operatorname{mid}(P_{i+2};P_i,P_{i+1})$로 두고 $B_i$의 XOR 누적 배열 $S$를 만든다. 또한

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

이므로 $P_R$에 관한 항을 $i=L,\cdots,R-3$에 대해 다시 XOR하면 중간 항이 모두 사라지고

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

만 남는다.

따라서 $R-L+1\leq3$이면 답은 $0$이고, 그 외에는

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

가 답이다. 전처리는 $O(N)$, 각 질의는 $O(1)$이며 전체 시간 복잡도는 $O(N+Q)$이다.

Solution written by GPT5