[SDS 알고리즘 특강 대비] 1517 버블소트 (인덱스트리, 구간압축)

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

 

 

2517 달리기 문제와 푸는 방법이 동일함.

값 자체를 쫙 펼쳐서 인덱스 트리의 리프노드로 설정한다는 idea가 필요

Collection sort를 이용해 구간압축을 하고, 인덱스트리로 노드값을 ++해주면 됨.

 

달리기 문제를 6시간 전에 공부했어 어렵지 않게 풀어냄!

 

long을 int로 하는 실수만 제발 주의하자!

이 실수 계속함..!!

 

<내 정답 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static ArrayList<int[]> arr;
    static int[] tree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        N= Integer.parseInt(br.readLine());
        arr = new ArrayList<>();
        tree = new int[N * 4];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr.add(new int[] {i, Integer.parseInt(st.nextToken())});
        }
        Collections.sort(arr, (o1, o2) -> {
            return o1[1] - o2[1];
        });
        for(int i=0; i<N; i++) {
            arr.get(i)[1] = i;
        }
        Collections.sort(arr, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        long cnt = 0;
        for(int i=0; i<N; i++) {
            cnt += query(1, 0, N-1, arr.get(i)[1]+1, N-1 );
//            System.out.println(cnt);
            update(1, 0, N-1, arr.get(i)[1]);
        }
        System.out.println(cnt);

    }
    static int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0;
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        int mid = (start + end)/2;
        return query(node*2, start, mid, left, right)
                + query(node*2+1, mid+1, end, left, right);
    }
    static void update(int node, int start, int end, int idx) {
        if (idx < start || end < idx) {
            return;
        }
        tree[node] += 1;
        if (start != end) {
            int mid = (start + end)/2;
            update(node*2, start, mid, idx);
            update(node*2+1, mid+1, end, idx);
        }
    }


}