답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/3006 풀이 : 세그먼트 트리 문제입니다. 각 숫자가 자신의 자리를 찾아가는데 항상 작은 숫자는 왼쪽 큰 숫자는 오른쪽으로 가기 때문에 홀수번째 일때는 왼쪽숫자의 갯수, 짝수번째는 오른쪽 숫자의 갯수로 옮기는 횟수를 쉽게 구할 수 있습니다. 각 숫자의 위치를 따로 저장해주고 세그먼트 트리에 각 숫자의 위치의 값을 1로 채웁니다. 그다음 세그먼트 트리를 활용하여 1. 홀수번째 : 찾으려는 값의 왼쪽 범위의 구간합 2. 짝수번째 : 찾으려는 값의 오른쪽 범위의 구간합 을 구하시면 됩니다. 구하신 후에는 찾으려는 값의 세그먼트 트리에 저장된 정보를 0으로 바꾸고 업데이트 시키시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 ..