ABABAB

각 값 $x$에 대해 $\operatorname{first}(x)$와 $\operatorname{last}(x)$를 각각 $x$가 처음 등장하는 위치와 마지막으로 등장하는 위치라고 하자. 또한 위치 $t$에 대해 $\operatorname{prev}(t)$를 $t$보다 앞에서 $A_t$가 마지막으로 등장한 위치로 정의한다. 그러한 위치가 없다면 $\operatorname{prev}(t)=0$으로 둔다.

다음 조건을 만족하는 위치 $p,q,t$가 존재하는지 판별하는 것으로 문제를 바꿀 수 있다.

• $p<q$는 어떤 값 $x$가 등장하는 서로 연속한 두 위치이다.
• $\operatorname{first}(x)<\operatorname{prev}(t)<p<t<q<\operatorname{last}(A_t)$.

원래 조건을 만족하는 값들을 $x,y$라고 하자. 선택된 두 번째 $x$보다 뒤에서 처음 등장하는 $y$의 위치를 $t$로 잡는다. $t$의 바로 왼쪽과 오른쪽에 있는 $x$의 등장 위치를 각각 로 잡으면 는 서로 연속하며, 보다 이전의 같은 값은 보다 앞에 존재한다. 따라서 위 조건이 성립한다.

반대로 위 조건이 성립하면 다음 여섯 위치를 선택할 수 있다.

$$\operatorname{first}(x),\quad \operatorname{prev}(t),\quad p,\quad t,\quad q,\quad \operatorname{last}(A_t).$$

이들은 엄격히 증가하며 값이 $x,A_t,x,A_t,x,A_t$ 순서로 나타난다. 사이에는 가 없으므로 도 자동으로 성립한다.

각 위치 $t$는 다음과 같은 직사각형을 만든다고 생각하자.

• 첫 번째 좌표의 구간은 $[\operatorname{prev}(t)+1,t-1]$이다.
• 두 번째 좌표의 구간은 $[t+1,\operatorname{last}(A_t)-1]$이다.

위치 $q$를 왼쪽에서 오른쪽으로 훑는다. $p=\operatorname{prev}(q)$라 두면 $p,q$는 $A_q$가 등장하는 서로 연속한 두 위치이다. 점 를 포함하는 직사각형들의 가중치 최댓값이 보다 크면 정답은 이다.

이를 위해 첫 번째 좌표를 관리하는 세그먼트 트리를 사용한다. 직사각형은 첫 번째 좌표 구간을 덮는 $O(\log N)$개의 노드에 추가한다. 각 노드는 $(\text{가중치},\text{만료 시각})$을 저장하는 최대 힙을 가진다. 위치 $t$의 직사각형은 시각 $t+1$에 추가되고 시각 부터 사용할 수 없으므로, 힙의 원소가 만료되었을 때 지연 삭제한다.

점 $p$를 질의할 때는 루트에서 $p$에 해당하는 리프까지의 노드만 확인하면 된다. 각 노드에서 만료된 원소를 제거한 뒤 남은 가중치의 최댓값을 취한다.

각 직사각형은 $O(\log N)$개의 힙에 들어가며 각 힙 연산에는 $O(\log N)$이 걸린다. 따라서 전체 시간 복잡도는 $O(N\log^2N)$, 공간 복잡도는 이다.

Solution written by GPT5.6