[백준 - 7578] 공장 - Java

https://www.acmicpc.net/problem/7578

7578번: 공장

 

이해하고 나면 플레치고 굉장히 단순한 인덱스트리 응용문제이다.

 

 

A를 도는 인덱스를 a, B의 인덱스를 b라고 할 때,

a = 1 일 때 b = 3이다.

update를 한 후 b+1부터 끝까지의 부분합을 구하면

크로스 되어있는 선의 개수를 알 수 있다. 

 

a = 1, b = 3 일때는 첫 연결선이기 때문에 아무것도 겹치는 선이 없다. 

 

 

a = 2, b = 1 일 때는 query가 1을 return 한다. 

 

인덱스 트리를 사용해서 이걸 쉽게 알 수 있도록 한다. 

 

 

 

a = 3, b = 4 일 때는 꼬인 선이 없다

 

a = 4, b = 2일 때는 꼬인 선이 두개 있다. 

 

 

a = 5, b = 5 일 때는 꼬인 선이 없다.

 

 

 

public class Main {
    static int[] A;
    static HashMap<Integer, Integer> B;
    static long[] tree;
    static int S;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        B = new HashMap<>();
        S = 1;
        while(S<N) S*=2;
        tree = new long[2*S+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            B.put(Integer.parseInt(st.nextToken()), i);
        }

        long res = 0;
        for(int i=0; i<N; i++){
            int b = B.get(A[i]);
            // index b update
            update(1, S, 1, b+1, 1);
            // j+1 ~ S 까지 query
            res += query(1, S, 1, b+2, S);
        }
        System.out.println(res);
    }

    static void update(int left, int right, int node, int target, int diff){
        if(target < left || target > right) return;
        else{
            tree[node] += diff;
            if(left!=right){
                int mid = (left+right)/2;
                update(left, mid, 2*node, target, diff);
                update(mid+1, right, 2*node+1, target, diff);
            }
        }
    }

    static long query(int left, int right, int node, int queryLeft, int queryRight){
        if(queryLeft > right || queryRight < left) return 0;
        else if(queryLeft <= left && queryRight >= right) return tree[node];
        else {
            int mid = (left+right)/2;
            long leftRes = query(left, mid, 2*node, queryLeft, queryRight);
            long rightRes = query(mid+1, right, 2*node+1, queryLeft, queryRight);
            return leftRes+rightRes;
        }
    }
}