2517 달리기

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

문제

---

KOI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 
각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 
자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 
반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 
이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다. 

각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 
현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 
각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 
예를 들어, 4번째로 달리고 있는 
평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 
평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.

선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.

---

입력

첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 
이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 
각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.

---

출력

각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.

---

예제 입력1

8
2
8
10
7
1
9
4
15

---

예제 출력1

1
1
1
3
5
2
5
1

---

• Visit를 체크하고 구간합을 구하는 문제이다.
• Visit 체크는 update
• Visit의 합 query → 노란 형광펜 부분의 합이다.
  
  
• 풀이 소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main_2517 {
    static int query(int[] visit, int node, int start, int end, int leftSearch
            , int rightSearch) {
        if (end < leftSearch || start > rightSearch) {
            return 0;
        }
        if (leftSearch <= start && rightSearch >= end) {
            return visit[node];
        }

        int mid = (start + end) / 2;
        int leftNodeIndex = 2 * node;
        int rightNodeIndex = 2 * node + 1;
        int leftNode =query(visit, leftNodeIndex, start, mid, leftSearch
                , rightSearch);
        int rightNode =query(visit, rightNodeIndex, mid + 1, end, leftSearch
                , rightSearch);
        return leftNode + rightNode;
    }

    static void update(int[] visit, int node, int start, int end, int index
            , int value) {
        if (start > index || end < index) {
            return;
        }
        if (start == end) {
            visit[node] = value;
            return;
        }

        int mid = (start + end) / 2;
        int leftNodeIndex = node * 2;
        int rightNodeIndex = node * 2 + 1;

        update(visit, leftNodeIndex, start, mid, index, value);		
        update(visit, rightNodeIndex, mid + 1, end, index, value);
        visit[node] = visit[leftNodeIndex] + visit[rightNodeIndex];
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N + 1];
            int[] answer = new int[N + 1];
            Map<Integer, Integer> indexMap = new HashMap<>();

            for (int i = 1; i <= N; i++) {
                arr[i] = Integer.parseInt(br.readLine());
                indexMap.put(arr[i], i);
            }
            int h = (int) Math.ceil(Math.log(N) / Math.log(2));
            int treeSize = (1 << (h + 1));
            int[] visit = new int[treeSize];
            int[] sortedArr = Arrays.stream(arr).sorted().toArray();
            for (int k = 1; k <= N; k++) {
                indexMap.put(sortedArr[k], k);
            }
            int start = 0;
            int result = 0;
            for (int i = 1; i <= N; i++) {
                start = indexMap.get(arr[i]);								
                update(visit, 1, 1, N, start, 1);
                result =query(visit, 1, 1, N, start, N);
                answer[i] = result;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= N; i++) {
                sb.append(answer[i]);
                sb.append("\n");
            }
            bw.write(sb.toString());
            bw.flush();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}