키 관리

컴퓨터 과학에서 이진 탐색 트리는 각 노드가 키와 연결된 이진 트리다. 노드의 키는 왼쪽 서브트리의 모든 키보다 크고, 오른쪽 서브트리의 모든 키보다 작다. 이진 탐색 트리는 데이터를 삽입하거나 삭제하고, 검색도 지원하는 동적 집합을 구현하는 데 흔히 쓰인다.

키 집합에서 특정 키를 찾을 때, 이진 탐색 트리는 보통 단순 탐색 알고리즘보다 성능이 좋다. 노드의 값과 비교한 뒤 서브트리로 내려갈 때, 다른 서브트리의 값들과는 비교할 필요가 없기 때문이다. 트리가 균형 잡혀 있으면 평균 비교 횟수는 트리 크기에 대해 로그 수준이다. 하지만 트리가 편향되면 효과가 떨어지고, 극단적인 경우 시간 복잡도가 선형으로 나빠진다. 악의적인 공격자는 나쁜 키 삽입 순서를 만들어 이 약점을 악용할 수 있다. 이진 탐색 트리가 자가 균형을 갖추지 않으면 결과 트리가 한쪽으로 치우쳐, 애플리케이션의 성능이 크게 떨어진다.

서버가 이진 탐색 트리로 동적 집합을 유지하는 상황을 생각해 보자. 이 트리는 단순한 삽입 알고리즘을 쓴다. 이 알고리즘은 기존 노드를 옮기지 않고, 알맞은 위치에 새 키를 리프로 붙인다. 그림 6은 이 단순 삽입 알고리즘으로 새 키가 트리에 들어가는 과정을 보여 준다.

(a) 삽입 전	(b) 삽입 후

그림 6: 단순 삽입 알고리즘의 실행 예시.

이제 클라이언트가 키를 연속으로 보내고, 서버는 그 키를 하나씩 삽입한다. 삽입 순서 중 특정 구간은 다시 배열할 수 있고, 그 결과 트리가 최대한 균형에 가까워지도록 하려 한다. 일부 삽입을 재배열한 뒤 결과 트리에서 노드 깊이의 합이 가능한 최솟값을 구하라. 노드의 깊이는 그 노드에서 루트까지 가는 경로에 있는 노드의 개수이다.

첫째 줄에 삽입할 키의 개수 $n$ $(1 \leq n \leq 10^5)$이 주어진다.

둘째 줄에는 순서대로 삽입할 키 $a_1, a_2, \cdots, a_n$ $(1 \leq a_i \leq n)$이 주어진다. 삽입하는 키는 모두 서로 다르다.

셋째 줄에는 재배열할 수 있는 삽입 구간을 나타내는 두 정수 $l$과 $r$ $(1 \leq l \leq r \leq n, r - l + 1 \leq 200)$이 주어진다. 키 $a_l, a_{l+1}, \cdots, a_r$의 삽입 순서를 바꿀 수 있다.

결과 이진 탐색 트리에서 노드 깊이의 합의 최솟값을 한 줄에 출력한다.

첫 번째 예시에서 재배열 후 최적의 삽입 순서는 [2,4,1,7,3,5,8,6]이다. 결과 이진 탐색 트리는 그림 7과 같다.

그림 7: 첫 번째 예시의 최적 이진 탐색 트리.