문제 링크
- http://icpc.me/16979
사용 알고리즘
- 모스 알고리즘
- 세그먼트 트리
시간복잡도
- $O((N+Q) \sqrt N log N)$
풀이
모스 알고리즘 + 세그먼트 트리(or 펜윅 트리)로 풀 수 있습니다.
모스 알고리즘을 사용할 것이기 때문에 구간의 왼쪽/오른쪽에 원소가 추가/제거되는 것, 총 4가지만 처리해주면 됩니다.
어떻게 처리할지 생각하기 전에, 수열의 값들을 좌표 압축을 하고 시작합시다.
기본적으로 구간 양끝에 원소가 추가되는 경우에는 해당 원소로 인해 생기는 inversion의 개수를 정답에 더해줄 것이고, 제거되는 경우에도 해당 원소로 인해 생기는 inversion의 개수를 정답에서 빼줄 것입니다.
어떤 원소 X가 왼쪽에 추가되는 경우에는 X보다 큰 원소의 개수를 더해주면 됩니다.
오른쪽에 추가되는 경우에는 X보다 작은 원소의 개수를 더해주면 됩니다.
어떤 원소 X가 왼쪽에서 제거되는 경우에는 X보다 큰 원소의 개수를 빼주면 되고, 오른쪽에서 제거되는 경우에는 X보다 작은 원소의 개수를 빼주면 됩니다.
이때 X보다 큰/작은 원소의 개수는 세그먼트 트리(or 펜윅 트리)를 이용해 구간합을 구하는 것으로 쉽게 처리할 수 있습니다.