BOJ 25649 Ternary Search

어떤 배열 $v$를 감소하다가 증가하는 수열로 만드는 최소 교환 횟수를 구할 수 있으면, 같은 배열을 증가하다가 감소하는 수열로 만드는 횟수는 $v$의 값을 $10^9 - v$로 바꿔서 같은 과정으로 구할 수 있습니다.

$v$를 감소하다가 증가하는 수열로 만들기 위해 필요한 교환 횟수는 다음과 같이 분석할 수 있습니다.

• 먼저 $v$의 최댓값 $v_m$은 무조건 전체 $v$에서 맨 왼쪽이나 맨 오른쪽으로 이동해야 합니다. 둘 중 최적인 것은 양쪽 중에서 수의 개수가 적은 쪽을 고르는 것입니다.
• 그 이후에 나머지 값들을 감소하다가 증가하는 아무 수열로 만들면 전체 $v$도 감소하다가 증가하는 수열이 되므로, $v_m$은 나머지 원소의 비용에 관여하지 않습니다. 따라서 $v_m$을 제거하고 재귀할 수 있습니다.
• 이를 다시 정리해 보면, 총 교환 횟수는 각 인덱스 $i$에 대해 “$v_i$의 왼쪽에 있으면서 $v_i$보다 작은 수의 개수"와 “$v_i$의 오른쪽에 있으면서 $v_i$보다 작은 수의 개수” 중 최솟값의 합이 됩니다.

이제 배열의 오른쪽 끝에 값을 추가하면서 위의 값을 모두 얻는 방법을 생각해 봅시다.

$v_i$의 왼쪽에 있으면서 $v_i$보다 작은 수의 개수는 한 번 결정되면 변하지 않습니다. $v_i$의 오른쪽에 있으면서 $v_i$보다 작은 수의 개수는 그 수보다 작은 수가 들어올 때마다 1 증가하는데, 이 값이 왼쪽 값 이상이 되면 $v_i$에서의 최적값은 더 이상 업데이트되지 않습니다.

따라서, 0과 1을 저장하는 합 세그먼트 트리를 만들고, 이전 배열의 답에 새로운 수보다 큰 수의 개수를 세어 더해주는 방법을 사용할 수 있습니다. 크기 순으로 $j$번째 수가 추가될 때 세그먼트 트리의 $j$번째 원소를 1로 만들고, $j+1$번째부터 끝까지의 합을 더해준 뒤, 더 이상 업데이트가 없는 원소들을 다시 0으로 만들어 주면 됩니다.

각 원소에 대해 업데이트를 멈춰야 하는 인덱스는, 별도의 합 세그먼트 트리에서 크기 순으로 값을 추가하면서 $v_i$의 왼쪽 개수를 구한 뒤에, 그 개수의 2배가 되는 지점을 세그먼트 트리 워크로 찾아서 저장해 두면 됩니다.

이 모든 과정을 구현하면 전체 알고리즘은 $\mathcal{O}(n \log n)$에 동작합니다. 시간 제한이 꽤 빡빡하므로 비효율적인 구현이 들어가지 않도록 주의합니다.