정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 1. 풀이 inversion 개수를 구하는 문제. 강사님이 merge sort를 구현하면서 inversion을 구할 수 있다고 하셨고, 이해도 갔지만 구현이 어려울 것 같았다. 그래서 ICPC를 준비하며 봤던 내용으로 인덱스 트리 / 펜윅 트리를 이..