백준 7578: 공장

풀이

inversion counting 세그먼트 트리를 사용해서 풀었다.
공장 두번째 라인의 인덱스 번호를 빠르게 조회하기 위해 HashMap을 사용하였다.

코드

import java.io.*;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) throws IOException {
//        System.out.println(solution(new String[][]{{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL","SFO"}}));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n=Integer.parseInt(br.readLine());
        tree=new int[n*4];
        arr1=new int[n+1];
        map=new HashMap<>();

        st=new StringTokenizer(br.readLine());
        int idx=1;
        while(st.hasMoreTokens()){
            arr1[idx++]=Integer.parseInt(st.nextToken());
        }

        st=new StringTokenizer(br.readLine());
        idx=1;
        while(st.hasMoreTokens()){
            map.put(Integer.parseInt(st.nextToken()),idx++);
        }

        long ans=0;

        for(int i=1;i<n+1;i++){
            int num=arr1[i];
            idx=map.get(num);

            ans+=sum(1,n,1,idx+1,n);

            update(1,n,1,idx,1);
        }

        System.out.println(ans);
    }

    static int[] tree,arr1;
    static Map<Integer,Integer> map;

    static void update(int s,int e ,int node,int idx,int val){
        if(s>idx || idx>e)return;

        if(s==e){
            tree[node]+=val;
            return;
        }

        int mid=(s+e)>>1;
        update(s,mid,node*2,idx,val);
        update(mid+1,e,node*2+1,idx,val);
        tree[node]=tree[node*2]+tree[node*2+1];
    }

    static int sum(int s,int e,int node,int l,int r){
        if(e<l || s>r)return 0;

        if(l<=s && e<=r){
            return tree[node];
        }

        int mid=(s+e)>>1;
        return sum(s,mid,node*2,l,r)+sum(mid+1,e,node*2+1,l,r);
    }
}

/*
* 5
132 392 311 351 231
392 351 132 311 231
* */

# 세그먼트트리