Barbera

필요한 배경지식 세그먼트 트리 Inversion Counting Inversion은 다음과 같이 정의됩니다. 길이가 N인 배열 A[1], A[2], ..., A[N]이 주어질때, $ i A[j] $를 만족할때 $A[i]$와 $A[j]$는 Inversion관계이다. Inversion Counting은 위에서 설명한 Inversion관계의 총 개수를 찾는 문제 입니다. 배열이 정렬이 되어 있을때는 Inversion Counting이 0이 되지만 역순으로 정렬되어 있다면 최대가 됩니다. Inversion쌍을 구하기 위한 방법으로 완전탐색을 생각해보면 \( O(N^{2}) \)의 시간복잡도로 모든 쌍을 비교해 볼 수 있지만 대부분의 문제에서 시간안에 해결할 수 없습니다. 이 문제..