꼬인 전선

현재 위치에서 선택할 수 있는 번호

위치 $p$까지 왼쪽에서 오른쪽으로 답을 정한다고 하자. $r_i$를 아직 배치하지 않은 $i$번 작업의 개수라 하자. $r_i$는 $0,1,2$ 중 하나이다.

$d \geq p$에 대해 다음 여유도를 정의한다.

마감 위치가 $d$ 이하인 모든 남은 작업은 $p,p+1,\cdots,d$ 안에 들어가야 하므로 항상 $S(d)\geq0$이어야 한다.

현재 위치 $p$에 전선 $i$를 하나 배치한 뒤 $p+1$로 이동한다고 하자. 새 여유도는 다음과 같이 변한다.

• $d<b_i$이면 $S(d)$가 $1$ 감소한다.
• $d\geq b_i$이면 $S(d)$가 변하지 않는다.

$z$를 $S(z)=0$인 가장 작은 $z\geq p$라 하자. 전체 남은 작업 수와 남은 위치 수가 같으므로 $S(2N)=0$이고, $z$는 항상 존재한다.

전선 $i$를 현재 위치에 배치한 뒤에도 가능한 배치가 남는 조건은 정확히 다음 두 조건이다.

• $a_i\leq p$이고 $r_i>0$이다.
• $b_i\leq z$이다.

두 번째 조건이 필요하다는 것은 여유도 변화에서 바로 알 수 있다. 충분성은 단위 작업의 구간 매칭에 대한 Hall 조건으로 보일 수 있다. 현재 위치를 제거했을 때 새로 빡빡해질 수 있는 Hall 조건은 왼쪽 끝이 현재 위치인 구간뿐이며, 이 조건들이 바로 위의 여유도 조건이다.

따라서 매 위치에서 위 조건을 만족하는 가장 작은 전선 번호를 선택하면 사전 순 최솟값을 얻는다.

자료 구조

두 개의 세그먼트 트리를 사용한다.

첫 번째 트리는 모든 $S(d)$를 저장한다. 구간 덧셈과 $p$ 이상에서 값이 $0$인 첫 위치 찾기를 지원한다. 전선 $i$를 선택하면 구간 $[p,b_i-1]$에 $-1$을 더한다.

두 번째 트리는 마감 위치 $b_i$를 인덱스로 사용한다. $a_i\leq p$이고 $r_i>0$인 전선 $i$에 대해 위치 $b_i$에 값 $i$를 저장하고, 나머지는 무한대로 둔다. 구간 $[p,z]$의 최솟값이 현재 선택할 번호이다. 전선을 두 번 사용하면 해당 위치의 값을 무한대로 바꾼다.

각 위치에서 세그먼트 트리 연산을 상수 번 수행하므로 시간 복잡도는 $O(N\log N)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6