코후닝

알고리즘 분류: 세그먼트 트리, 자료구조문제 링크: https://www.acmicpc.net/problem/7578     어떻게 풀어야 할까.. 막막하지만역전(inversion) 이라는 개념을 알고 있으면 정말 쉬워진다.역전(inversion)은 배열에서 앞에 있는 값이 뒤에 있는 값보다 큰 경우를 말하기도 하고,원본 배열과 비교 배열에서 원본 배열의 요소가 비교 배열의 요소에서 얼마나 뒤로 떨어져 있는지를 의미하기도 한다. 풀이는 굉장히 간단한데, 그냥 inversion된 애들이 얼마나 inversion 되었는지 세어주면 된다. 어차피 모든 요소들이 매칭이 되어야하므로어떤 요소가 inversion 되지 않았다면(뒤에 위치하고 있다면)?어떤 요소는 반드시 inversion 되어 있는 상태가 된다. 위..