ABAB

먼저 값들을 좌표 압축한다. 이후 같은 값인지 여부만 사용하므로 좌표 압축은 답에 영향을 주지 않는다.

각 값 $x$에 대해 다음 두 값을 관리한다.

• $\operatorname{last}[x]$: 수열 전체에서 $x$가 마지막으로 등장하는 위치.
• $\operatorname{recent}[x]$: 현재 위치보다 앞에서 $x$가 가장 최근에 등장한 위치.

현재 $k$번 위치를 처리하며 $x=A_k$라 하자. $x$가 이전에 등장한 위치를 $i=\operatorname{recent}[x]$라 하면, 다음 조건을 만족하는 값 가 존재할 때 정답은 이다.

$$i<\operatorname{recent}[y]<k<\operatorname{last}[y].$$

실제로 $j=\operatorname{recent}[y]$, $l=\operatorname{last}[y]$로 두면

$$i<j<k<l,\qquad A_i=A_k=x,\qquad A_j=A_l=y$$

가 된다. 또한 $\operatorname{recent}[y]>i=\operatorname{recent}[x]$이므로 $x\neq y$이다.

따라서 현재 위치보다 뒤에 다시 등장할 값들 중 $\operatorname{recent}$가 가장 큰 값을 빠르게 알아내면 된다.

어떤 값 $x$가 $t$번 위치에 등장했고 $\operatorname{last}[x]>t$라면, 쌍 $(t,x)$를 스택의 뒤에 추가한다. 추가되는 위치 $t$는 항상 증가하므로, 유효한 쌍들 가운데 위치가 가장 큰 쌍은 항상 스택의 가장 뒤쪽에 있다.

$k$번 위치를 처리하기 전에 스택의 뒤에서 다음 중 하나를 만족하는 쌍 $(t,y)$를 계속 제거한다.

• $\operatorname{recent}[y]\neq t$. 이후에 $y$가 다시 등장하여 이 쌍이 오래된 정보가 된 경우이다.
• $\operatorname{last}[y]\leq k$. 가 번 위치보다 뒤에 더 이상 등장하지 않는 경우이다.

제거가 끝난 뒤 스택의 마지막 쌍은, 현재 위치보다 뒤에 다시 등장하는 모든 값 중 가장 큰 최근 등장 위치를 나타낸다. 따라서 $x$가 이전에 등장했고 스택의 마지막 위치가 $\operatorname{recent}[x]$보다 크면 YES이다.

이제 이 판정이 모든 가능한 답을 찾음을 보이자. 답이 되는

$$i<j<k<l,\qquad A_i=A_k=x,\qquad A_j=A_l=y$$

가 존재한다고 하자. $j$보다 뒤에 처음 등장하는 $x$의 위치를 $k'$라 하고, 그 직전 $x$의 등장 위치를 $i'$라 하자. 그러면

$$i'\leq i<j<k'\leq k<l$$

이다. $k'$번 위치를 처리할 때 $y$의 최근 등장 위치는 $j$ 이상이고, 마지막 등장 위치는 $l$ 이상이다. 따라서 스택에는 위치가 $i'$보다 큰 유효한 쌍이 존재하며 알고리즘이 반드시 를 출력한다.

각 쌍은 스택에 한 번 추가되고 한 번만 제거되므로 좌표 압축 이후의 스캔은 $O(N)$이다. 좌표 압축을 포함한 전체 시간 복잡도는 $O(N\log N)$, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6