Median 2

짝수 크기의 접두사에서 가운데 두 원소가 $l<u$라면 둘 사이에는 이미 등장한 값이 없다. 다음 중앙값이 내부의 값이면 그 값을 직접 추가해야 하고, 끝점이면 반대쪽 바깥에 값을 하나 추가한다. 앞에서 만든 $C_i^A$가 정확히 이 세 경우를 나타낸다. 따라서 모든 접두사 중앙값이 주어진 기록과 일치한다.

로 둔다. 같은 논리로 위치 $i$의 값 구간 $C_i^B$와 값 $v$의 위치 구간 $L_v^B\le \operatorname{pos}(v)\le R_v^B$를 얻는다. 이번에는 $Y_i$가 접미사에 등장해야 하므로 $\operatorname{pos}(Y_i)\ge i$이고, 짝수 길이 접미사의 가운데 두 값 $l<u$ 사이의 값들은 그 접미사에 없어야 하므로 $\operatorname{pos}(v)\le i-1$이다.

두 방향의 조건을 합치면 각 위치에는 하나의 값 구간 $\ell_i\le P_i\le r_i$가 생기고, 각 값에는 하나의 위치 구간 $L_v\le \operatorname{pos}(v)\le R_v$가 생긴다. 구간의 교집합이 비어 있으면 즉시 불가능하다.

이제 왼쪽부터 위치 $i=1,2,\cdots,N$을 채운다. $L_v=i$가 된 값 $v$를 활성화한다. 활성화되어 아직 사용되지 않은 값 중 $\ell_i\le v\le r_i$를 만족하는 값만 현재 위치에 놓을 수 있다. 그중 $R_v$가 가장 작은 값을 선택한다.

이 그리디에는 다음 교환 성질이 성립한다. 현재 위치 $i$에서 어떤 완성 가능한 답이 값 $p$를 사용하고, 그리디가 값 $q$를 골랐다고 하자. 그 답에서 $q$가 놓인 위치를 $j\ge i$라 하자. 그리디의 선택으로 $R_q\le R_p$이다. $q$가 $j$에 놓일 수 있으므로 $j\le R_q$, 따라서 $j\le R_p$이고 $L_p\le i\le j$도 성립한다.

남는 것은 위치 $j$의 값 구간이다. 중앙값 기록에서 만들어지는 구간에는 다음 성질이 있다. $i<j$이고 두 값이 모두 위치 $i$에서 가능하며, 그중 $q$는 위치 $j$에서도 가능한데 $p$는 불가능하다면 $R_p<R_q$이다. 이를 확인하려면 $C_i^A,C_i^B$가 변하는 세 경우만 보면 된다. 한 경계가 $p$와 $q$ 사이를 지나 $p$만 제외하는 최초의 순간에는, $p$가 접두사의 가운데 값으로 확정되어 그 시점까지 등장해야 하거나, $p$가 짝수 길이 접미사의 두 가운데 값 사이에 들어가 그 시점 이전에 등장해야 한다. 두 경우 모두 그 순간이 $R_p$를 결정한다. 반면 $q$는 그 뒤의 위치 $j$에서도 가능하므로 $R_q\ge j$이다. 따라서 $R_p<R_q$이다.

지금은 $R_q\le R_p$이므로 위 상황은 일어날 수 없다. 따라서 $p$도 위치 $j$에 놓을 수 있다. 답에서 $p$와 $q$를 교환하면 그리디의 첫 선택을 포함하는 완성 가능한 답을 얻는다. 이를 반복하면 그리디가 실패하지 않는 한 항상 전체 순열을 완성할 수 있다.

구현에서는 열린 값 구간에 대한 $L_v^A$의 range chmax와 $R_v^B$의 range chmin이 필요하다. 모든 갱신이 끝난 뒤 점 값만 필요하므로 lazy 값만 저장하는 세그먼트 트리로 각각 $O(N\log N)$에 처리할 수 있다.

마지막 그리디에서는 값 $v$를 좌표 $v$에 두고, 활성화된 값의 리프에 $(R_v,v)$를 저장하는 세그먼트 트리를 사용한다. 위치 $i$에서 $[\ell_i,r_i]$의 최소 쌍을 구하면 바로 선택할 값을 얻는다. 트리 전체의 최소 deadline이 $i$보다 작아졌다면 이미 놓을 수 없는 값이 생긴 것이므로 불가능하다.

구성이 끝난 뒤 만들어진 순열의 모든 접두사와 접미사 중앙값을 Fenwick tree의 $k$번째 원소 탐색으로 다시 확인할 수 있다. 잘못된 입력에 대한 구현상 검산으로 사용할 수 있으며 복잡도는 그대로 $O(N\log N)$이다.

시간 복잡도는 $O(N\log N)$, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6