꼬인 전선

각 전선 $i$를 현재 두 끝점 사이의 구간으로 생각하자.

도달 가능한 배치

다음 보조정리를 사용한다.

처음에 $i$번 전선이 $[a_i,b_i]$를 연결한다고 하자. 길이 $2N$의 수열 $C$에서 각 번호가 정확히 두 번 나타난다. 각 $i$에 대해 $i$가 나타나는 두 위치가 모두 $[a_i,b_i]$ 안에 있는 것과, $C$가 연산으로 도달 가능한 것은 동치이다.

한 번의 연산에서 두 전선의 새 끝점은 각각 그 전선의 기존 두 끝점 사이에 있다. 따라서 도달 가능한 모든 배치는 위 조건을 만족한다.

역방향은 표준적인 uncrossing 보조정리로 증명할 수 있다. 현재 배치와 목표 배치의 같은 번호 간선을 겹쳐 그리면 짝수 길이의 교대 사이클들로 분해된다. 현재 배치와 목표 배치가 다르면, 어떤 교대 사이클에는 현재의 교차 간선 두 개가 존재하며 그 교차를 문제의 방향으로 풀어도 각 목표 간선은 같은 번호의 새 구간 안에 남는다. 이 연산은 현재 구간 길이의 합을 엄격히 감소시킨다. 이를 반복하고 구간 길이의 합에 대해 귀납하면 목표 배치에 도달한다.

따라서 문제는 다음 스케줄링 문제와 같다.

• 전선 $i$는 번호가 $i$인 동일한 작업 두 개를 가진다.
• 두 작업은 각각 $a_i$ 이상 $b_i$ 이하의 위치에 배치해야 한다.
• 모든 위치에는 작업 하나를 배치한다.
• 완성된 번호 수열을 사전 순으로 최소화한다.

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

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

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

$$S(d)=d-p+1-\sum_{b_i\leq d}r_i.$$

마감 위치가 $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