algospot 삽입 정렬 시간 재기 (문제 ID: MEASURETIME)c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/MEASURETIME

algospot.com :: MEASURETIME

길이 N인 수열 A[]가 주어지고, A[]를 삽입정렬했을때 정렬 과정에서 숫자들을 총 몇 번이난 옮기는지 계산하는 문제이다.

 

일단 모든 노드의 값이 0인 팬윅트리를 생성한다. A[]의 요소를 왼쪽부터 탐색해서 각 값에 해당하는 팬윅트리 노드들의 값을 1씩 증가시킨다. 또한 자신보다 큰 값이 나왔던 횟수를 구하기 위해 전체 횟수 합에서 자신이하의 값이 나온 횟수합을 뺀다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/24.%20segmentTree/MEASURETIME.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2