백준 10090: Counting Inversions

문제

풀이

병합 정렬 과정에서 num[l] >= num[r] 인 경우는
l ~ mid 까지는 num[r]보다 크다는 뜻이므로 정답에 mid-l+1을 더해준다.

---

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
//        System.out.println(solution(relation,2,3));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n=Integer.parseInt(br.readLine());
        num=new int[n+1];
        int size=(int)Math.pow(2,(int)Math.ceil(Math.log(n)/Math.log(2))+1);
        minTree=new int[size];
        cnt=new int[1000001];

        st=new StringTokenizer(br.readLine());
        for(int i=1;i<n+1;i++){
            num[i]=Integer.parseInt(st.nextToken());
        }
        
        ans=0;
        inversion(1,n);
        System.out.println(ans);
    }

    static int n;
    static long ans;
    static int[] num,minTree,cnt;

    static void inversion(int s,int e){
        if(s>=e)return;
        int mid=(s+e)>>1;

        inversion(s,mid);
        inversion(mid+1,e);

        int l=s;
        int r=mid+1;
        int idx=0;
        int[] tmp=new int[e-s+1];

        while(l<=mid && r<=e){
            if(num[l]<num[r]){
                tmp[idx++]=num[l++];
            }
            else{
                ans+=mid-l+1;
                tmp[idx++]=num[r++];
            }
        }

        while(l<=mid){
            tmp[idx++]=num[l++];
        }
        while(r<=e){
            tmp[idx++]=num[r++];
        }

        for(int i=s;i<=e;i++)num[i]=tmp[i-s];

    }

}

#병합정렬(merge sort)