치터와 쿼리

거짓말쟁이 구간을 $[L,R]$이라 하자. $i$번 사람이 거짓말쟁이라는 조건은 $i \in [L,R]$이고, $i$번 사람의 주장이 참이라는 조건은 $[l_i,r_i]$가 $[L,R]$과 교차하는 것이다. 두 조건의 참과 거짓은 서로 반대여야 한다.

각 사람에 대해 다음 네 값을 정의한다.

$$a_i=\min(i,r_i),\qquad b_i=\max(i,l_i),\qquad c_i=\min(i,l_i),\qquad d_i=\max(i,r_i).$$

$i$번 사람이 구간 안에 있으면서 주장이 참인 경우는 정확히 $L \leq a_i$이고 $b_i \leq R$인 경우이다.

$i$번 사람이 구간 밖에 있으면서 주장도 거짓인 경우는 다음 세 형태 중 하나이다.

• $R<c_i$.
• $d_i<L$.
• $a_i<L \leq R<b_i$. 마지막 형태는 $i$와 주장 구간이 서로 떨어져 있을 때 그 사이에 거짓말쟁이 구간이 놓이는 경우이다.

따라서 다음 값을 정의한다.

$$A=\min_i d_i,\qquad B=\max_i c_i,$$ $$M(L)=\max_{a_i<L} b_i,\qquad G(L)=\min_{a_i\geq L} b_i.$$

$M(L)$의 집합이 비어 있으면 $0$, $G(L)$의 집합이 비어 있으면 $N+1$로 정의한다.

구간 $[L,R]$이 정답일 필요충분조건은 다음과 같다.

$$L\leq A,\qquad \max(B,L,M(L))\leq R<G(L).$$

첫 번째 부등식은 모든 $d_i<L$ 형태를 막는다. $R\geq B$는 모든 $R<c_i$ 형태를 막는다. $R\geq M(L)$는 $a_i<L \leq R<b_i$ 형태를 막는다. 마지막으로 $R<G(L)$는 $L\leq a_i$이고 $b_i\leq R$인 사람을 없앤다. 따라서 이 조건들은 위의 모든 모순을 정확히 제거한다.

이제 동적으로 $M(L)$과 $G(L)$을 다룬다. 각 좌표 $x$에 대해 다음 두 값을 유지한다.

$$\mathrm{hi}_x=\max_{a_i=x} b_i,\qquad \mathrm{lo}_x=\min_{a_i=x} b_i.$$

그러면 $M(L)$은 $\mathrm{hi}$의 접두 최댓값이고, $G(L)$은 $\mathrm{lo}$의 접미 최솟값이다. 같은 $a_i$를 가진 여러 사람은 multiset으로 관리한다. $A$와 $B$도 각각 $d_i$와 $c_i$의 multiset으로 관리한다.

좌표 $1,2,\cdots,N$을 크기 약 $\sqrt N$인 블록으로 나눈다. 블록 $[s,e]$ 안의 각 후보 $L$에 대해 다음 값을 미리 계산한다.

$$X_L=\max\left(L,\max_{s\leq x<L}\mathrm{hi}_x\right),\qquad Y_L=\min_{L\leq x\leq e}\mathrm{lo}_x.$$

$X_L$과 $Y_L$은 모두 $L$에 대해 감소하지 않는다. 또한 $X_L<Y_L$인 위치들을 따로 저장한다.

현재 블록보다 앞의 $\mathrm{hi}$ 최댓값을 $P$, 뒤 블록들의 $\mathrm{lo}$ 최솟값을 $S$라 하자. 이 블록의 후보 $L$이 가능하려면

$$\max(B,P,X_L)<\min(S,Y_L)$$

이어야 한다. 이는 다음 네 조건과 동치이다.

• $\max(B,P)<S$.
• $X_L<S$.
• $Y_L>\max(B,P)$.
• $X_L<Y_L$.

$X_L,Y_L$이 단조이므로 두 번의 이분 탐색으로 가능한 위치 범위를 구하고, 저장해 둔 $X_L<Y_L$ 위치가 그 범위에 있는지 확인할 수 있다. 찾았다면

$$R=\max(B,P,X_L)$$

로 두면 된다. $L\leq A$인 후보만 조사한다.

한 번의 주장 변경은 기존 좌표 $a_i$와 새로운 좌표 $a_i$가 속한 블록만 바꾼다. 따라서 최대 두 블록을 다시 계산하면 된다.

각 변경의 시간 복잡도는 $O(\sqrt N\log N)$이고, 전체 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6