백준 14458 소가 길을 건너간 이유 10

https://www.acmicpc.net/problem/14458 14458번: 소가 길을 건너간 이유 10 소가 왜 길을 건너는지는 미해결 난제지만, 농부 존의 소들이 길을 자주 건넌다는 것은 잘 알려진 사실이다. 소들이 길을 건너는 일이 너무 잦아서 건너면서 부딪히는 일도 생기는데, 존은 이 상 www.acmicpc.net 초기 상태의 가로지르는 쌍은, inversion counting이므로 nlogn에 처리할 수 있다. 세그트리나 BIT, 또는 병합 정렬로 구현할 수 있다. 그러면 초기 상태가 아닌, k개를 옮긴 상황은 어떻게 생각해야 할까? 아이디어만 설명할 것이기 때문에, 편의상 왼쪽의 목초지는 1...N이라고 두자. 또, 마지막 n-k개를 옮기는 상황이나 처음의 k개를 옮기는 상황이나 같은데..

원문링크 : 백준 14458 소가 길을 건너간 이유 10